Score : $400$ points

问题描述

存在一个 $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)$ 上。
玩家可以进行以下移动零次或多次。

• 首先，指定移动方向：向上、向下、向左或向右。
• 然后，按照指定方向持续移动，直到碰到岩石为止。正式表述为：
  • 如果沿移动方向的下一个方格为冰，进入该方格并继续移动；
  • 如果沿移动方向的下一个方格为石，留在当前方格并停止移动。

请计算玩家能够接触到（经过或停留于）的冰方格数量。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:50:50