Grid Ice Floor

题目描述

有一个 $N \times M$ 的网格，一个玩家站在其上。
令 $(i,j)$ 表示该网格中从上数第 $i$ 行、从左数第 $j$ 列的方格。
该网格的每个方格要么是冰要么是石头，用长度为 $M$ 的 $N$ 个字符串 $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

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

215

提示

$3 \le N,M \le 200$ $S_i$ 是长度为 $M$ 且由 # 和 $.$ 组成的字符串。 若 $i=1$、$i=N$、$j=1$ 或 $j=M$ 则方格 $(i, j)$ 是石头。 方格 $(2,2)$ 是冰。例如，玩家可以通过如下移动在 $(5,5)$ 停下：

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

玩家可以通过如下移动经过 $(2,4)$：

$(2,2) \rightarrow (2,5)$，在此过程中经过 $(2,4)$。

玩家不能经过或停在 $(3,4)$。

标签: AtCoder|abc311D

来源

AtCoder|abc311D