2015 - 冰上滑动
描述

有一个 N×MN \times M 的矩阵,并且有一个玩家站在上面。

其中 (i,j)(i, j) 表示矩阵的第 ii 行第 jj 列。

矩阵被表示为 NN 个字符串 S1S2S3...SNS_1 S_2S_3...S_N,每个字符串长 MM 个字符。


矩阵每个格子都是冰或者岩石:如果 SiS_i 的第 jj 个字符,即 (i,j)(i, j) 对应的字符为 `.`,那么 (i,j)(i, j) 是冰;如果是 `#`,(i,j)(i, j) 就是岩石。


这个矩阵的一周(第 11 行、第 NN 行、第 11 列,第 MM 列)均为岩石。

玩家起始所站的点 (2,2)(2, 2) 恒为冰。


玩家可以移动零次或任意次,每次移动需要先选定一个方向(上下左右),并且一直沿着这个方向移动直到遇到岩石(或不是冰)。


计算出玩家可以抵达或途径的所有格点(包括滑过的)。


输入

N M

S1

S2

...

SN

第一行两个正整数 NNMM,表示矩阵的长宽。

第二行到第 N+1N + 1 行,每行一个长 MM 的字符串,表示矩阵内容(代表矩阵内容的字符)。


输出

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

样例

输入
复制

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

输出
复制

12

输入
复制

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

输出
复制

215
提示

对于 100%100\% 的数据:3N,M200 3 \le N, M \le 200

SiS_i 是长为 MM 的字符串,仅包含 `.` 和 `#`。

矩阵的边缘都是 `#`(岩石),且 (2,2)(2,2) 处一定为 `.`(冰)。

 样例1解释

比如玩家可以经过 (5,5)(5,5) 通过这样移动:(2,2)(2, 2)(5,2)(5, 2)(5,5)(5, 5)

玩家也可以经过 (2,4)(2, 4)(2,2)(2, 2)(2,5)(2, 5),途经 (2,4)(2, 4)

但玩家无法到达 (3,4)(3, 4)


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 33
通过次数 22