102323: [AtCoder]ABC232 D - Weak Takahashi

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

问题描述

有一个$H \times W$的正方形网格，有$H$行水平行和$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
.....