题目描述

縦 $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)$ から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $C_{1,\ 1}\ \ldots\ C_{1,\ W}$ $\vdots$ $C_{H,\ 1}\ \ldots\ C_{H,\ W}$

输出格式

答えを出力せよ。

题目大意

输入一个 $H\times W$ 的字符矩阵，. 表示空地，# 表示障碍，从 $(1,1)$ 出发，只能向下或向右走，问最多经过几个格子。

Translated by @$\tt{\_YXJS\_}$.

3 4
.#..
..#.
..##

4

1 1
.

1

5 5
.....
.....
.....
.....
.....

9

提示

制約

• $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}\ =$ .

Sample Explanation 1

例えば $ (1,\ 1)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (2,\ 2)\ \rightarrow\ (3,\ 2) $ と進むことで、$4$ マス通ることができます。 $5$ マス以上通ることはできないので、$4$ と出力します。