/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
縦 H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 C_{i, j} で表され、C_{i, j} = . ならばマス (i, j) は空きマスであり、C_{i, j} = # ならばマス (i, j) は壁です。
高橋君がグリッド上を歩こうとしています。彼がマス (i, j) にいるとき、マス (i, j + 1) またはマス (i + 1, j) に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。
高橋君がマス (1, 1) から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？
制約
- 1 \leq H, W \leq 100
- H, W は整数
- C_{i, j} =
.または C_{i, j} =#(1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
出力
答えを出力せよ。
入力例 1
3 4 .#.. ..#. ..##
出力例 1
4
例えば (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) と進むことで、4 マス通ることができます。
5 マス以上通ることはできないので、4 と出力します。
入力例 2
1 1 .
出力例 2
1
入力例 3
5 5 ..... ..... ..... ..... .....
出力例 3
9
Score : 400 points
Problem Statement
There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.
Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.
When starting on (1, 1), at most how many squares can Takahashi visit before he stops?
Constraints
- 1 \leq H, W \leq 100
- H and W are integers.
- C_{i, j} =
.or C_{i, j} =#. (1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
Input
Input is given from Standard Input in the following format:
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
Output
Print the answer.
Sample Input 1
3 4 .#.. ..#. ..##
Sample Output 1
4
For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.
He cannot visit 5 or more squares, so we should print 4.
Sample Input 2
1 1 .
Sample Output 2
1
Sample Input 3
5 5 ..... ..... ..... ..... .....
Sample Output 3
9