有一个 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 的字符串,表示矩阵内容(代表矩阵内容的字符)。
输出玩家能触及的格点数。
6 6 ###### #....# #.#..# #..#.# #....# ######
12
21 25 ######################### #..............###...#### #..............#..#...### #........###...#...#...## #........#..#..#........# #...##...#..#..#...#....# #..#..#..###...#..#.....# #..#..#..#..#..###......# #..####..#..#...........# #..#..#..###............# #..#..#.................# #........##.............# #.......#..#............# #..........#....#.......# #........###...##....#..# #..........#..#.#...##..# #.......#..#....#..#.#..# ##.......##.....#....#..# ###.............#....#..# ####.................#..# #########################
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)。
时间限制 | 1 秒 |
内存限制 | 128 MB |