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$ 的字符串，表示矩阵内容（代表矩阵内容的字符）。

输出格式

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

输入输出样例 #1

输入 #1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

输出 #1

12

输入输出样例 #2

输入 #2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

输出 #2

215

说明/提示

对于 $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)$。