AT_abc311_d [ABC311D] Grid Ice Floor

题目描述

有一个 $N \times M$ 的矩阵,并且有一个玩家站在上面。 其中 $(i, j)$ 表示矩阵的第 $i$ 行第 $j$ 列。 矩阵被表示为 $N$ 个字符串 $S_1 S_2S_3...S_N$,每个字符串长 $M$ 个字符。 矩阵每个格子都是冰或者岩石:如果 $S_i$ 的第 $j$ 个字符,即 $(i, j)$ 对应的字符为 `.`,那么 $(i, j)$ 是冰;如果是 `#`,$(i, j)$ 就是岩石。 这个矩阵的一周(第 $1$ 行、第 $N$ 行、第 $1$ 列,第 $M$ 列)均为岩石。 玩家起始所站的点 $(2, 2)$ 恒为冰。 玩家可以移动零次或任意次,每次移动需要先选定一个方向(上下左右),并且一直沿着这个方向移动直到遇到岩石(或不是冰)。 计算出玩家可以抵达或途径的所有格点(包括滑过的)。

输入格式

``` N M S1 S2 ... SN ``` 第一行两个正整数 $N$ 和 $M$,表示矩阵的长宽。 第二行到第 $N + 1$ 行,每行一个长 $M$ 的字符串,表示矩阵内容(代表矩阵内容的字符)。

输出格式

输出玩家能触及的格点数。

说明/提示

对于 $100\%$ 的数据: $ 3 \le N, M \le 200 $ $S_i$ 是长为 $M$ 的字符串,仅包含 `.` 和 `#`。 矩阵的边缘都是 `#`(岩石),且 $(2,2)$ 处一定为 `.`(冰)。 #### 样例1解释 比如玩家可以经过 $(5,5)$ 通过这样移动: $(2, 2)$ → $(5, 2)$ → $(5, 5)$ 玩家也可以经过 $(2, 4)$: $(2, 2)$ → $(2, 5)$,途经 $(2, 4)$。 但玩家无法到达 $(3, 4)$。