冰面网格

题目描述

有一个 $N \times M$ 的网格,一名玩家站在上面。

用 $(i,j)$ 表示该网格第 $i$ 行(从上往下数)、第 $j$ 列(从左往右数)的格子。

网格中的每个格子要么是冰,要么是岩石,用 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\dots,S_N$ 表示如下:

• 若 $S_i$ 的第 $j$ 个字符为 .,则格子 $(i,j)$ 是冰;
• 若 $S_i$ 的第 $j$ 个字符为 #,则格子 $(i,j)$ 是岩石。

网格的外围(第 1 行、第 $N$ 行、第 1 列、第 $M$ 列的所有格子)都是岩石。

初始时,玩家站在冰面格子 $(2,2)$ 上。

玩家可以进行以下移动零次或多次:

首先,指定移动方向:上、下、左或右。

然后,沿着该方向一直移动,直到撞上岩石。形式化地说,重复执行以下过程:

• 若移动方向上的下一个格子是冰,则移动到该格子并继续移动;
• 若移动方向上的下一个格子是岩石,则停在当前格子,移动结束。

求玩家能够接触(经过或停留)到的冰面格子的数量。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

以整数形式输出答案。

样例

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

12

例如,玩家可以按如下方式移动到 $(5,5)$:

$(2,2) \rightarrow (5,2) \rightarrow (5,5)$。

玩家可以按如下方式经过 $(2,4)$:

$(2,2) \rightarrow (2,5)$,途中经过 $(2,4)$。

玩家无法经过或停留于 $(3,4)$。

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

215

数据范围

• $3 \le N,M \le 200$
• $S_i$ 是长度为 $M$、由 # 和 . 组成的字符串。
• 若 $i=1$、$i=N$、$j=1$ 或 $j=M$,则格子 $(i,j)$ 是岩石。
• 格子 $(2,2)$ 是冰。