/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は古い建物の中で迷路に閉じ込められてしまいました。
この建物は N 行 M 列のグリッドで表されます。上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。グリッドの i 行目の状態は文字列 S_i で表され、S_i の j 文字目が # ならマス (i, j) は壁、. ならマス (i, j) は通路です。
高橋君は現在マス (1, 1) におり、右下のマス (N, M) にある出口を目指しています。
高橋君は、現在いるマスから上下左右に隣接するマス1つへ1回の操作で移動できます。ただし、グリッドの範囲外へ移動することはできません。移動先のマスが通路であれば、そのまま移動します。移動先のマスが壁であれば、ハンマーを使ってその壁を破壊して通路に変えたうえで移動します。壁を1つ破壊するたびに、破壊回数が 1 加算されます。一度破壊して通路に変わったマスは、以降も通路のままです。ハンマーの使用回数に上限はなく、また移動の回数にも上限はありません。
ハンマーで壁を何度でも破壊できるため、高橋君は必ずマス (N, M) に到達できます。高橋君がマス (1, 1) からマス (N, M) に到達するまでに破壊する壁の数の最小値を求めてください。
なお、マス (1, 1) とマス (N, M) は必ず通路であることが保証されています。
制約
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- N, M は整数
- S_i (1 \leq i \leq N) は
#と.からなる長さ M の文字列 - S_1 の 1 文字目は
. - S_N の M 文字目は
.
入力
N M S_1 S_2 \vdots S_N
- 1 行目には、グリッドの行数 N と列数 M が、スペース区切りで与えられる。
- 1 + i 行目 (1 \leq i \leq N) には、グリッドの i 行目の状態を表す長さ M の文字列 S_i が与えられる。S_i の j 文字目がマス (i, j) の状態を表し、
#は壁、.は通路を意味する。
出力
高橋君がマス (1, 1) からマス (N, M) に到達するために破壊する必要がある壁の数の最小値を 1 行で出力せよ。
入力例 1
3 5 ...#. .###. ...#.
出力例 1
1
入力例 2
3 3 ... ... ...
出力例 2
0
入力例 3
5 7 ..#.#.# .#...#. ##.#.## .#...#. ..#.#..
出力例 3
2
入力例 4
10 10 .......... .########. .......... .########. .......... .########. .......... .########. .......... ..........
出力例 4
0
入力例 5
1 1 .
出力例 5
0
入力例 6
3 5 ...#. .###. ...#.
出力例 6
1
入力例 7
3 3 ... ... ...
出力例 7
0
入力例 8
5 7 .#.#.#. .#.#.#. .#.#.#. .#.#.#. .......
出力例 8
0
入力例 9
10 10 .......... .########. .......... ########.# .......... .########. .......... ########.# .......... ..........
出力例 9
0
入力例 10
1 1 .
出力例 10
0
Score : 400 pts
Problem Statement
Takahashi is trapped in a maze inside an old building.
The building is represented as a grid with N rows and M columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j). The state of the i-th row of the grid is represented by the string S_i: if the j-th character of S_i is #, then cell (i, j) is a wall; if it is ., then cell (i, j) is a passage.
Takahashi is currently at cell (1, 1) and aims to reach the exit at cell (N, M) in the bottom-right corner.
In one operation, Takahashi can move from his current cell to one of the four adjacent cells (up, down, left, or right). However, he cannot move outside the grid. If the destination cell is a passage, he simply moves there. If the destination cell is a wall, he uses his hammer to destroy the wall, turning it into a passage, and then moves there. Each time a wall is destroyed, the destruction count increases by 1. A cell that has been destroyed and turned into a passage remains a passage thereafter. There is no limit on the number of times the hammer can be used, and there is no limit on the number of moves.
Since Takahashi can destroy walls as many times as needed, he can always reach cell (N, M). Find the minimum number of walls Takahashi needs to destroy to travel from cell (1, 1) to cell (N, M).
It is guaranteed that cell (1, 1) and cell (N, M) are always passages.
Constraints
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- N, M are integers
- S_i (1 \leq i \leq N) is a string of length M consisting of
#and. - The 1st character of S_1 is
. - The M-th character of S_N is
.
Input
N M S_1 S_2 \vdots S_N
- The first line contains the number of rows N and the number of columns M of the grid, separated by a space.
- The (1 + i)-th line (1 \leq i \leq N) contains a string S_i of length M representing the state of the i-th row of the grid. The j-th character of S_i represents the state of cell (i, j), where
#means a wall and.means a passage.
Output
Print in one line the minimum number of walls Takahashi needs to destroy to travel from cell (1, 1) to cell (N, M).
Sample Input 1
3 5 ...#. .###. ...#.
Sample Output 1
1
Sample Input 2
3 3 ... ... ...
Sample Output 2
0
Sample Input 3
5 7 ..#.#.# .#...#. ##.#.## .#...#. ..#.#..
Sample Output 3
2
Sample Input 4
10 10 .......... .########. .......... .########. .......... .########. .......... .########. .......... ..........
Sample Output 4
0
Sample Input 5
1 1 .
Sample Output 5
0
Sample Input 6
3 5 ...#. .###. ...#.
Sample Output 6
1
Sample Input 7
3 3 ... ... ...
Sample Output 7
0
Sample Input 8
5 7 .#.#.#. .#.#.#. .#.#.#. .#.#.#. .......
Sample Output 8
0
Sample Input 9
10 10 .......... .########. .......... ########.# .......... .########. .......... ########.# .......... ..........
Sample Output 9
0
Sample Input 10
1 1 .
Sample Output 10
0