G - Escape Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

ある日、映画館を訪れた高橋君は、館内の全ての床に、最寄りの非常口の方向を示す矢印を描くことにしました。

縦 H マス、横 W マスのグリッドが与えられます。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
各マスの状態は、次のいずれかの文字 S_{i,j} で表されます。

  • . : 通路マス
  • # : 壁マス
  • E : 非常口

任意の通路マス (i, j) に対して、(i, j) と最寄りの非常口との距離 d(i, j) を次のように定義します。

  • (i, j) からスタートして、上下左右に隣接する 壁マスでないマス へ移動することを繰り返して非常口に到達する際の、必要な最小の移動回数。

ここで、入力として与えられるグリッドにおいて、全ての通路マスに対し d(i, j) が定義可能であることが保証されます。すなわち、すべての通路マス (i, j) において、通路マスのみを経由することで到達可能な非常口が少なくとも 1 つ存在します。

このとき、以下の条件を満たすように、すべての通路マスに対して「上下左右いずれかの方向の矢印」を書き込んでください。

  • 各通路マス (i, j) について、(i,j) にいる状態から開始して、以下の操作を d(i, j) 回行うことで非常口に到達することができる。
    • 現在いるマスに書かれた矢印の方向に従って 1 マス移動する。(ただし、壁マスやグリッドの外へは移動できない。)

制約

  • 2 \leq H \leq 1000
  • 2 \leq W \leq 1000
  • S_{i,j} は ., # または E
  • 全ての通路マス (i, j) について、そこからいずれかの非常口に到達することが可能である
  • H, W は整数である

入力

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

H W
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

出力

矢印を書き込んだ後のマス (i, j) の状態を T_{i,j} とする。T_{i,j} は次のいずれかである。

  • ^ : 上矢印が書かれた通路マス
  • v : 下矢印が書かれた通路マス
  • < : 左矢印が書かれた通路マス
  • > : 右矢印が書かれた通路マス
  • # : 壁マス
  • E : 非常口

これらを以下の形式で出力せよ。

T_{1,1}T_{1,2}\dots T_{1,W}
T_{2,1}T_{2,2}\dots T_{2,W}
\vdots
T_{H,1}T_{H,2}\dots T_{H,W}

答えが複数ある場合は、どれを出力しても正答とみなされる。

入力例 1

3 4
...E
.#..
....

出力例 1

>>>E
^#>^
>>>^

出力例の (2, 3) について問題文の条件が成立することを確認します。(2, 3) と最寄りの非常口の距離は 2 です。そして、出力例のように書き込まれた矢印に従って移動することで 2 回の移動で非常口に到達することができます。
他の通路マスについても問題文の条件が成立することが確認できます。

入力例 2

3 2
##
##
##

出力例 2

##
##
##

通路マスおよび非常口が存在しない場合もあります。

入力例 3

7 20
....................
..#..#..####..#E##..
..#..#..#..#..#.....
..E###..#..#..####..
.....#..#..E.....#..
.....#..####..####..
....................

出力例 3

>v<<<<<>>>>>>>>v<<<<
>v#^<#^^####v^#E##vv
>v#^<#v^#>v#vv#^<<<<
>>E###vv#>v#vv####^<
>>^<<#vv#>>E<<<<<#^<
>>^<<#vv####^<####^<
>>^<<<<<>>>>^<<<<<^<

Score : 400 points

Problem Statement

One day, Takahashi visited a cinema and decided to draw arrows on every floor tile, each pointing toward the nearest emergency exit.

You are given a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell is represented by one of the following characters S_{i,j}:

  • . : corridor cell
  • # : wall cell
  • E : emergency exit

For any corridor cell (i, j), define d(i, j), the distance to the nearest emergency exit, as follows:

  • Starting from (i, j), repeatedly move to an adjacent non-wall cell in one of the four cardinal directions (up, down, left, right) until you reach an emergency exit. d(i, j) is the minimum number of moves required.

It is guaranteed that d(i, j) is definable for every corridor cell in the given grid; that is, every corridor cell (i, j) has at least one emergency exit reachable by passing through only corridor cells.

Write exactly one arrow (up, down, left, or right) in every corridor cell so that the following condition holds:

  • For every corridor cell (i, j), if you start at (i, j) and perform the following action d(i, j) times, you reach an emergency exit:
    • Move one cell in the direction of the arrow written in your current cell. (You cannot move into a wall cell or outside the grid.)

Constraints

  • 2 \le H \le 1000
  • 2 \le W \le 1000
  • Each S_{i,j} is ., #, or E.
  • Every corridor cell (i, j) has at least one reachable emergency exit.
  • H and W are integers.

Input

The input is given from Standard Input in the following format:

H W
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

Output

Let T_{i,j} be the state of cell (i, j) after writing the arrows. T_{i,j} is one of the following:

  • ^ : corridor cell with an upward arrow
  • v : corridor cell with a downward arrow
  • < : corridor cell with a leftward arrow
  • > : corridor cell with a rightward arrow
  • # : wall cell
  • E : emergency exit

Output the grid in the following format:

T_{1,1}T_{1,2}\dots T_{1,W}
T_{2,1}T_{2,2}\dots T_{2,W}
\vdots
T_{H,1}T_{H,2}\dots T_{H,W}

If multiple solutions exist, any of them will be accepted.

Sample Input 1

3 4
...E
.#..
....

Sample Output 1

>>>E
^#>^
>>>^

Let us verify the condition for (2, 3) in the sample output. The distance from (2, 3) to the nearest emergency exit is 2, and following the arrows written in the sample output leads to an emergency exit in two moves.
The condition can be verified for every other corridor cell as well.

Sample Input 2

3 2
##
##
##

Sample Output 2

##
##
##

There may be cases with no corridor cells or emergency exits.

Sample Input 3

7 20
....................
..#..#..####..#E##..
..#..#..#..#..#.....
..E###..#..#..####..
.....#..#..E.....#..
.....#..####..####..
....................

Sample Output 3

>v<<<<<>>>>>>>>v<<<<
>v#^<#^^####v^#E##vv
>v#^<#v^#>v#vv#^<<<<
>>E###vv#>v#vv####^<
>>^<<#vv#>>E<<<<<#^<
>>^<<#vv####^<####^<
>>^<<<<<>>>>^<<<<<^<