(問題 23)グリッド01BFS 1 PHP編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
整数 N, M が与えられます。N 行 M 列のグリッドがあります。上から i (1 ≦ i ≦ N) 行目、左から j (1 ≦ j ≦ M) 列目のマスを (i, j) と表記します。
また、N 個の長さ M の文字列 L_1,...,L_N が与えられます。L_i (1 ≦ i ≦ N) の j (1 ≦ j ≦ M) 文字目が # のときは (i, j) に障害物があることを、. のときは (i, j) に障害物がないことを意味します。
今回は障害物を破壊することができ、破壊するとそのマスも通行可能になります。
左右上下の 4 方向に移動を繰り返し行い (1, 1) から (N, M) に移動を行う時障害物を壊す回数の最小値を求めてください。
- 入力される値
-
N M
L_1
L_2
...
L_N
1 行目には 2 つの整数 N, M が与えられます。
1 + i (1 ≦ i ≦ N) 行目には 1 つの文字列 L_i が与えられます。
入力は合計で 1 + N 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ N ≦ 300
- 1 ≦ M ≦ 300
- L_i は
#と.で構成された長さ M の文字列 (1 ≦ i ≦ N)- L_1 の 1 文字目は
.
- 入力例1
-
5 5
.....
###.#
...#.
.#..#
#.##.
- 出力例1
-
2
- 入力例2
-
1 11
...........
- 出力例2
-
0
