AT_abc232_d [ABC232D] Weak Takahashi

题目描述

有一个由 $H$ 行 $W$ 列组成的 $H \times W$ 的网格。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。
每个格子的状态由字符 $C_{i, j}$ 表示，若 $C_{i, j} = \texttt{.}$，则格子 $(i, j)$ 是空格；若 $C_{i, j} = \texttt{\#}$，则格子 $(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}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

1 1
.

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

9

说明/提示

限制条件

• $1 \leq H, W \leq 100$
• $H, W$ 为整数
• $C_{i, j} = \texttt{.}$ 或 $C_{i, j} = \texttt{\#}$（$1 \leq i \leq H, 1 \leq j \leq W$）
• $C_{1, 1} = \texttt{.}$

样例解释 1

例如，可以按 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2)$ 的顺序前进，这样可以经过 $4$ 个格子。无法经过 $5$ 个或更多格子，因此输出 $4$。

由 ChatGPT 4.1 翻译