Score : $400$ points

问题描述

存在一个 $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)$ 开始出发，在他停止行走之前，最多能访问多少个方格？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:06:51