AT_s8pc_5_e Broken Skateboard

[problemUrl]: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_e 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 $ 点\] - 追加の制約はない. ### Sample Explanation 1 !\[ \](https://img.atcoder.jp/s8pc-5/fe10790bc085cdf9081a2d91f3597a64.png) スケートリンクの状態は上図のようになっている. マス $ (2,\ 4) $ からスタートすると, 上図のように $ 8 $ 秒かかる. ### Sample Explanation 2 !\[ \](https://img.atcoder.jp/s8pc-5/59c02527d9a8aa4441e839fc8a94b15c.png) スケートリンクの状態は上図のようになっている. マス $ (1,\ 1) $ からスタートすると, 上図のように $ 15 $ 秒かかる.