/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点：800 点
問題文
E869120 は H 行 W 列のマス目から成るスケートリンクに行くことを考えている. 左上のマスは (1, 1) 右下のマスは (H, W) である.
スケートリンクは 1 個のゴールのマス, いくつかの氷のマス, いくつかのコンクリートのマスから成る. 彼は特定の場所からスタートし, 最短の時間でゴールする予定である.
このスケートリンクは, 以下のような性質を持つ.
- 氷のマスは滑るので, コンクリートのマスまたはゴールのマスにたどり着くまで同じ方向に進み続ける. ただしスケートリンクの外に出ると, ゲームオーバーである.
- 人は, 止まっている時のみ進む方向を変えることができる.
- ゴールのマスの上に来ると, ゲームクリアである.
しかし、彼の持っているスケートボードは既に破壊寸前である. よって, 以下のように速度が変わってしまう.
- 彼は 1 マス動くのに k 秒かかる. 最初, k=1 である.
- 彼がコンクリートのマスの上に来て, 停止すると, k が 1 増える.
- 上下左右の 4 方向にしか動くことはできない.
彼はスケートリンクに行く前に, 全てのマス (i, j) について, マス (i, j) からスタートすると最短で何秒かかるかを知りたい.
彼の代わりにプログラムを書け.
入力
入力は以下の形式で標準入力から与えられる.
H W
c_{1,1}c_{1,2}c_{1,3} ... c_{1,W}
c_{2,1}c_{2,2}c_{2,3} ... c_{2,W}
c_{3,1}c_{3,2}c_{3,3} ... c_{3,W}
...
c_{H,1}c_{H,2}c_{H,3} ... c_{H,W}
1 行目には, スケートリンクの大きさ H, W が与えられる.
2 行目から H 行にわたって, スケートリンクの状態が与えられる. ただし, 各マスの状態は, 以下のような文字で表現される.
.は, 氷のマスを表す.#は, コンクリートのマスを表す.Gは, ゴールのマスを表す.
出力
以下の形式で出力せよ.
d_{1,1} d_{1,2} d_{1,3} ... d_{1,W}
d_{2,1} d_{2,2} d_{2,3} ... d_{2,W}
d_{3,1} d_{3,2} d_{3,3} ... d_{3,W}
...
d_{H,1} d_{H,2} d_{H,3} ... d_{H,W}
d_{i,j} は, マス (i, j) から出発する場合のゴールするまでの最短時間を表す.
ただし, どんな方法を使ってもゴールできない場合, d_{i,j} の値は -1 となる.
制約
- H は 1 以上 777 以下の整数.
- W は 1 以上 777 以下の整数.
- スケートリンクには 0 個以上 7 \ 777 個以下のコンクリートのマスが存在する.
- スケートリンクにはゴールのマスがちょうど 1 個存在する.
小課題
小課題 1 [40 点]
- H = 1.
- W \leq 17.
小課題 2 [160 点]
- H \leq 17.
- W \leq 17.
- スケートリンクには 77 個以下のコンクリートのマスが存在する.
小課題 3 [190 点]
- H \leq 177.
- W \leq 177.
- スケートリンクには 377 個以下のコンクリートのマスが存在する.
小課題 3 [410 点]
- 追加の制約はない.
入力例 1
6 6 ...... .#.... ...... ...... ...... ...#.G
出力例 1
-1 -1 -1 9 -1 5 -1 -1 -1 8 -1 4 -1 -1 -1 7 -1 3 -1 -1 -1 6 -1 2 -1 -1 -1 5 -1 1 7 6 5 2 1 0
スケートリンクの状態は上図のようになっている.
マス (2, 4) からスタートすると, 上図のように 8 秒かかる.
入力例 2
1 8 #####G##
出力例 2
15 10 6 3 1 0 1 3
スケートリンクの状態は上図のようになっている.
マス (1, 1) からスタートすると, 上図のように 15 秒かかる.
入力例 3
9 9 ....#..#. #........ ....#.... .#......# ...###... ##....#.# ....#...# #....#... .#.#..#.G
出力例 3
54 37 52 29 38 38 17 53 18 43 36 60 28 37 37 16 65 17 40 35 38 27 26 36 15 39 16 35 22 21 20 19 18 14 16 10 28 27 26 16 16 25 13 36 9 28 17 16 15 14 13 7 9 5 18 17 16 14 8 7 6 5 2 41 22 52 13 15 37 5 51 1 22 14 13 7 6 5 2 1 0
Max Score：800 points
Problem Statement
E869120 the Coder is thinking about going to a skating rink which size is H \times W. The upper-left cell is (1,1), and the lower-right cell is (H,W).
The skating rink consists of 1 goal cell, some ice cells and some concrete cells.
The skating rink has characteristics as follows:
- Skaters move to the same direction while they're moving on ice cells.
- Skaters can change direction if and only they are stopping.
- If the skater came on the goal cell, he/she completes the game. However, if the skater came outside the skating rink, he/she will no longer able to complete the game.
Moreover, his skateboard is broken, so the moving speed will change as follows:
- It takes k seconds to move one cell. Initially, k is 1.
- If the skateboard come on a concrete cell, k will increase by 1.
- He can move only 4 directions: up, down, left, right.
He want to know the minimum time to complete the game for each starting cell.
Please write the program instead of E869120.
Input
Input is given from Standard Input in the following format:
H W
c_{1,1}c_{1,2}c_{1,3} ... c_{1,W}
c_{2,1}c_{2,2}c_{2,3} ... c_{2,W}
c_{3,1}c_{3,2}c_{3,3} ... c_{3,W}
...
c_{H,1}c_{H,2}c_{H,3} ... c_{H,W}
In 1-st line, the size of the skating link H, W is given.
From 2-nd line to H+1-th line, the state of skating link is given. The state of each cell is represents as follows:
.means that the cell is an ice cell.#means that the cell is a concrete cell.Gmeans that the cell is a goal cell.
Output
Print H lines in the following format:
d_{1,1} d_{1,2} d_{1,3} ... d_{1,W}
d_{2,1} d_{2,2} d_{2,3} ... d_{2,W}
d_{3,1} d_{3,2} d_{3,3} ... d_{3,W}
...
d_{H,1} d_{H,2} d_{H,3} ... d_{H,W}
d_{i,j} means the minimum time if he starts from cell (i,j). If he cannot reach the goal cell from (i,j), the value of d_{i,j} is -1.
Constraints
- 1 \leq H \leq 777.
- 1 \leq W \leq 777.
- The number of concrete cells is not more than 7 \ 777.
- The number of goal cells is exactly 1.
Subtasks
Subtask 1 [40 points]
- H = 1.
- W \leq 17.
Subtask 2 [160 points]
- H \leq 17.
- W \leq 17.
- The number of concrete cells is not more than 77.
Subtask 3 [190 points]
- H \leq 177.
- W \leq 177.
- The number of concrete cells is not more than 377.
Subtask 4 [410 points]
- There are no additional constraints.
Sample Input 1
6 6 ...... .#.... ...... ...... ...... ...#.G
Sample Output 1
-1 -1 -1 9 -1 5 -1 -1 -1 8 -1 4 -1 -1 -1 7 -1 3 -1 -1 -1 6 -1 2 -1 -1 -1 5 -1 1 7 6 5 2 1 0
The above-mentioned picture represents the skating rink.
If he start from (2, 4), it takes 8 seconds.
Sample Input 2
1 8 #####G##
Sample Output 2
15 10 6 3 1 0 1 3
The above-mentioned picture represents the skating rink.
If he start from (1, 1), it takes 8 seconds.
Sample Input 3
9 9 ....#..#. #........ ....#.... .#......# ...###... ##....#.# ....#...# #....#... .#.#..#.G
Sample Output 3
54 37 52 29 38 38 17 53 18 43 36 60 28 37 37 16 65 17 40 35 38 27 26 36 15 39 16 35 22 21 20 19 18 14 16 10 28 27 26 16 16 25 13 36 9 28 17 16 15 14 13 7 9 5 18 17 16 14 8 7 6 5 2 41 22 52 13 15 37 5 51 1 22 14 13 7 6 5 2 1 0