0562 - 構成ゲー(迷路)

問題

壁と通路からなる迷路が与えられます．
迷路の外と壁は通ることができず，通路は通ることができます．
移動は上下左右の4方向に可能で移動にはコストが 1 かかります．
スタート地点からゴール地点に移動するとき，合計の移動コストが最小となるような 経路 を求めてください．

a

構成ゲーと呼ばれる解を復元するだけの問題であまり面白いものではないけれど解けないと

入力

W H
C1,1 C2,1 .. CW,1
:
C1,H C2,H .. CW,H

1 行目に迷路の横の大きさ W と 縦の大きさ H が整数で与えられる．
2 行目以降の H 行からなる迷路の情報が与えられる．
i 行目(1 <= i <= H) の j 文字目(1 <= j <= W) には (j, i) の情報が書かれている．
C_j,i は '.','#','S','G' のいずれかの文字からなり
'.' は通路，'#' は壁，'S'はスタート地点，'G' はゴール地点を表している．

制約

• 3 ≦ W, H ≦ 1000
• C_{j, i} は '.','#','S','G' のいずれかの文字
• スタート地点からゴール地点までの経路は必ず存在する

出力

H 行にスタート地点からゴール地点に移動する時，合計の移動コストが最小となるような経路を出力せよ．
スタート地点からゴール地点に行くまでに通る必要がある点は '*' を出力し，通らない地点は対応する迷路の文字を出力しろ．
'S' と 'G' はそのまま出力しなければならない．
合計の移動コストが最小となるような経路が複数ある場合どれを出力しても良い．

サンプル

入力1

5 5
S....
####.
.....
.#.#.
...G.

出力1

S****
####*
....*
.#.#*
...G*

入力2

5 5
S....
.....
.....
.....
....G

出力2

S*...
.**..
..**.
...**
....G

解説

出力2 について答えが複数あるがどれを出力しても良い．