Time Limit: 2 sec / Memory Limit: 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
.
,#
,<
,^
,>
, orv
. - 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