H - コンベア 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

縦 H マス、横 W マスの 2 次元グリッドがあります。
上から i 行目、左から j 列目のマスをマス (i, j) と表すことにします。
マス (i, j) の情報が文字 s_{i,j} により与えられます。 s_{i,j} は . , # , < , ^ , > , v のいずれかです。 # は入ることのできないマスであることを、 < , ^ , > , v の 4 つは一方通行のマスであることを、 . は何もないマスであることを表します。
あなたは # でないマスを 1 つ選びロボットを置いたあと、以下の操作を繰り返してロボットをマス (r, c) まで動かします。

  • 現在いるマスと上下左右に隣り合う、# でないマスに動かす。 このとき、グリッドの外に出てはいけない。

ただし、ロボットが一方通行のマスにいるときはその方向以外には動かすことができません。
より正確には、ロボットがマス (i, j) にいるとき、

  • s_{i,j} が < ならばマス (i, j - 1) 以外には動かすことができません。
  • s_{i,j} が ^ ならばマス (i - 1, j) 以外には動かすことができません。
  • s_{i,j} が > ならばマス (i, j + 1) 以外には動かすことができません。
  • s_{i,j} が v ならばマス (i + 1, j) 以外には動かすことができません。

# でない各マスについて、そのマスにロボットを置いたときに、ロボットをマス (r, c) まで動かせるかを判定してください。

制約

  • 1 \le H, W
  • H \times W \le 10^6
  • 1 \le r \le H
  • 1 \le c \le W
  • s_{i,j} は . , # , < , ^ , > , v のいずれか
  • s_{r,c} は # でない

入力

入力は以下の形式で標準入力から与えられる。

H W
r c
s_{1,1}\dots s_{1,W}
\vdots
s_{H,1}\dots s_{H,W}

出力

H 行にわたって、 W 文字の文字列を出力せよ。
i 行目の j 文字目には、 s_{i,j} が # である場合 # を、 s_{i,j} が # でない場合、ロボットをマス (i,j) からマス (r, c) まで動かせるならば o を、動かせないならば x を出力せよ。

入力例 1

3 3
1 1
..#
^^.
><.

出力例 1

oo#
ooo
xxo

ロボットをマス (3,3) に置いたとき、 (3,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1) と動かすことでロボットをマス (1,1) まで移動させることができます。 ロボットをマス (3,1) に置くと、一方通行のマスがあるためロボットをマス (1,1) まで移動させることができません。

入力例 2

10 12
9 1
#.^<..><<...
#<>.#<^.<<.^
^.<>.^.^.^>.
^.>#^><#....
.>.^>#...<<>
....^^.#<.<.
.>^..^#><#.^
......#>....
..<#<...^>^.
<..^>^^...^<

出力例 2

#xxxxxxxxxxx
#xxx#xxxxxxx
xooxxxxxxxxx
xox#xxx#xxxx
oooxx#xxxxxx
ooooxxx#xxxx
ooooox#xx#xx
oooooo#xxxxx
ooo#xoooxxxx
xooxooooooxx

入力例 3

15 20
13 9
####..<#^>#>.<<><^..
#.>#>.^#^.>><>...^..
>..<>.#.>.>.>...#..<
<^>.#..<>^#<#.>.<.^.
>#<^>.>#^>#^.^.#^><^
<^.^.#<...<.><#>...#
.<>....^..#>>#..>>><
.<#<^#.>#>^^.>.##.^<
.#.^.....<<#^#><^<<<
^.#>.#^.>.^.^<<>..><
.^#^<^^^<......^>.#^
.<..#>...^>^.^<..<.^
#.^.#..#.....>#.^^.>
.#^..>>><>>>^..#^.^^
.>#..<..<>.#>..^.#.^

出力例 3

####xxx#xx#xxxxxxxxx
#xx#xxx#xxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxx
xxxx#xxxxx#x#xxxxxxx
x#xxxxx#xx#xxxx#xxxx
xxoxo#xxxxxxxx#xxxx#
xxoooooxxx#xx#xxxxxx
xx#xo#ox#xxxxxx##xxx
x#xxooooooo#x#xxxxxx
xx#oo#ooooooxxxoooxx
xx#ooxoooooooooooo#x
xxoo#oooooooooooooox
#ooo#oo#ooooox#oooox
x#oooxxxxoooooo#ooox
xx#oooooooo#oooxo#ox

Score : 6 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a two-dimensional grid with H horizontal rows and W vertical columns.
Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
Square (i, j) is described by a character s_{i,j}, which is . , # , < , ^ , > , or v.
# represents a blocked square; each of <, ^, >, and v represents a square on which you can only go one way; . represents an empty square.
You will put a robot on a non-# square of your choice and then repeat the operation below to send the robot to Square (r, c).

  • Move the robot up, down, left, or right to an adjacent non-# square. The robot is not allowed to go out of the grid.

However, when the robot is on a one-way square, it can only go in the specified direction.
More formally, when a robot is on Square (i, j),

  • if s_{i,j} is <, the robot can only go to Square (i, j - 1);
  • if s_{i,j} is ^, the robot can only go to Square (i - 1, j);
  • if s_{i,j} is >, the robot can only go to Square (i, j + 1);
  • if s_{i,j} is v, the robot can only go to Square (i + 1, j).

For each non-# square, determine whether the robot can start at that square and reach Square (r, c).

Constraints

  • 1 \le H, W
  • H \times W \le 10^6
  • 1 \le r \le H
  • 1 \le c \le W
  • s_{i,j} is ., #, <, ^, >, or v.
  • s_{r,c} is not #.

Input

Input is given from Standard Input in the following format:

H W
r c
s_{1,1}\dots s_{1,W}
\vdots
s_{H,1}\dots s_{H,W}

Output

Print H lines containing W characters each.
The j-th character in the i-th line should be # if s_{i,j} is #; o if s_{i,j} is not # and the robot can reach from Square (i, j) to Square (r, c); and x if s_{i,j} is not # and the robot cannot reach from Square (i, j) to Square (r, c).

Sample Input 1

3 3
1 1
..#
^^.
><.

Sample Output 1

oo#
ooo
xxo

If the robot starts at Square (3, 3), it can reach (1, 1) as follows: (3,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1).
On the other hand, if it starts at Square (3, 1), it cannot reach (1, 1) because of the one-way squares.

Sample Input 2

10 12
9 1
#.^<..><<...
#<>.#<^.<<.^
^.<>.^.^.^>.
^.>#^><#....
.>.^>#...<<>
....^^.#<.<.
.>^..^#><#.^
......#>....
..<#<...^>^.
<..^>^^...^<

Sample Output 2

#xxxxxxxxxxx
#xxx#xxxxxxx
xooxxxxxxxxx
xox#xxx#xxxx
oooxx#xxxxxx
ooooxxx#xxxx
ooooox#xx#xx
oooooo#xxxxx
ooo#xoooxxxx
xooxooooooxx

Sample Input 3

15 20
13 9
####..<#^>#>.<<><^..
#.>#>.^#^.>><>...^..
>..<>.#.>.>.>...#..<
<^>.#..<>^#<#.>.<.^.
>#<^>.>#^>#^.^.#^><^
<^.^.#<...<.><#>...#
.<>....^..#>>#..>>><
.<#<^#.>#>^^.>.##.^<
.#.^.....<<#^#><^<<<
^.#>.#^.>.^.^<<>..><
.^#^<^^^<......^>.#^
.<..#>...^>^.^<..<.^
#.^.#..#.....>#.^^.>
.#^..>>><>>>^..#^.^^
.>#..<..<>.#>..^.#.^

Sample Output 3

####xxx#xx#xxxxxxxxx
#xx#xxx#xxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxx
xxxx#xxxxx#x#xxxxxxx
x#xxxxx#xx#xxxx#xxxx
xxoxo#xxxxxxxx#xxxx#
xxoooooxxx#xx#xxxxxx
xx#xo#ox#xxxxxx##xxx
x#xxooooooo#x#xxxxxx
xx#oo#ooooooxxxoooxx
xx#ooxoooooooooooo#x
xxoo#oooooooooooooox
#ooo#oo#ooooox#oooox
x#oooxxxxoooooo#ooox
xx#oooooooo#oooxo#ox