开始: 2024-06-12 00:00:00

(23-24赛季)稠州常规赛19

结束: 2024-06-15 00:00:00
当前  2025-01-24 17:44:49  类型: IOI  状态: 已经结束 

P1. 冰上滑动
描述

有一个 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

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

第二行到第 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
提交