問題
$H$ 列 $W$ 行からなる迷路が与えられる。 .はその場所が通れることを、#はその場所が通れないことを示している。移動は上下左右のみで斜めの移動は出来ないものとする。この迷路の左上から右下までの最短経路を*で示せ。ただし、左上から右下まで移動できない場合はNoを出力せよ。
入力
入力は以下の形式で標準入力から与えられる。
$H$ $W$
$l_{1,1}$ $l_{1,2}$ ... $l_{1,W}$
$l_{2,1}$ $l_{2,2}$ ... $l_{2,W}$
...
$l_{H,1}$ $l_{H,2}$ ... $l_{H,W}$
1行目に整数 $H$,$W$ がスペース区切りで与えられる。 その後 $H$ 行で迷路の構造が与えられる。
出力
迷路の左上から右下まで移動できる場合は最短経路を*で示せ。
移動できない場合はNoを出力せよ。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $3 \leq H, W \leq 100$
- 最短経路は二つ以上存在しないことが保証される。
- 左上と右下は . であることが保証される。
入出力例
入力例1
3 4 . . . . # # # . # # # .
出力例1
* * * * # # # * # # # *
入力例2
5 5 . . # . . # . . . . . # . # . . # # # . . # . . .
出力例2
* * # . . # * * * * . # . # * . # # # * . # . . *
入力例3
4 4 . . . . . . . . # # # # . . . .
出力例3
No
左上から右下まで移動する方法がないためNoを出力する。