4269: Weak Takahashi

# Weak Takahashi ### 内存 1024MB ### 时间 2S ## 题目描述 有一个 $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}$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例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