103113: [Atcoder]ABC311 D - Grid Ice Floor

Problem Statement

There is an $N \times M$ grid and a player standing on it.
Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by $N$ strings $S_1,S_2,\dots,S_N$ of length $M$ as follows:

• if the $j$-th character of $S_i$ is ., square $(i,j)$ is ice;
• if the $j$-th character of $S_i$ is #, square $(i,j)$ is rock.

The outer periphery of this grid (all squares in the $1$-st row, $N$-th row, $1$-st column, $M$-th column) is rock.

Initially, the player rests on the square $(2,2)$, which is ice.
The player can make the following move zero or more times.

• First, specify the direction of movement: up, down, left, or right.
• Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
  • if the next square in the direction of movement is ice, go to that square and keep moving;
  • if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

• $3 \le N,M \le 200$
• $S_i$ is a string of length $M$ consisting of # and ..
• Square $(i, j)$ is rock if $i=1$, $i=N$, $j=1$, or $j=M$.
• Square $(2,2)$ is ice.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

12

For instance, the player can rest on $(5,5)$ by moving as follows:

• $(2,2) \rightarrow (5,2) \rightarrow (5,5)$.

The player can pass $(2,4)$ by moving as follows:

• $(2,2) \rightarrow (2,5)$, passing $(2,4)$ in the process.

The player cannot pass or rest on $(3,4)$.

Sample Input 2

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

Sample Output 2

215

问题描述

有一个$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)$。

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

• 首先，指定移动方向：上、下、左或右。
• 然后，沿着该方向一直移动，直到玩家撞到岩石。具体来说，一直做以下操作：
  • 如果移动方向上的下一个方格是冰，移动到那个方格并继续移动；
  • 如果移动方向上的下一个方格是岩石，停留在当前方格并停止移动。

找出玩家可以触碰到的冰方格的数量（经过或停留在上面）。

限制条件

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

输入

输入从标准输入以以下格式给出：

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

输出

将答案作为整数打印。

样例输入1

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

样例输出1

12

例如，玩家可以通过以下方式在$(5,5)$休息：

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

玩家可以通过以下方式经过$(2,4)$：

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

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

样例输入2

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