4269: 最多能访问多少个格子

内存限制:1024 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:3 解决:1

题目描述

# Weak Takahashi ## 题目描述 有一个 $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)$ 开始行走,在他停止之前最多可以经过多少个格子?

输入

## 输入格式 输入按以下格式从标准输入给出: $H$ $W$ $C_{1,1}$ ... $C_{1,W}$ $\vdots$ $C_{H,1}$ ... $C_{H,W}$

输出

## 输出格式 输出所求答案。

样例输入 复制

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

样例输出 复制

4

提示

## 输入输出样例 ### 输入样例1 ``` 3 4 .#.. ..#. ..## ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 1 1 . ``` ### 输出样例2 ``` 1 ``` ### 输入样例3 ``` 5 5 ..... ..... ..... ..... ..... ``` ### 输出样例3 ``` 9 ``` ## 数据范围与提示 【样例1说明】 例如,通过 $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2)$ 的路径,小高可以经过 4 个格子。 他无法经过 5 个或更多格子,所以应输出 4。 【数据范围】 - $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} = '.'$。 ## 题目来源 ABC232D