← 返回题目列表

AtCoder · abc311_d

G. 网格冰地板

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个 N \times M 网格和站在其上的玩家。
让 (i,j) 表示位于 i从顶部开始的第行和 j- 该网格左侧的第列。
该网格的每个方格都是冰或岩石,用下式表示 N 字符串 S_1,S_2,\dots,S_N 长度 M 如下:

  • 如果 j第一个字符 S_i is .,方形 (i,j) 是冰;
  • 如果 j第一个字符 S_i is #,方形 (i,j) 很摇滚。

该网格的外周(网格中的所有方块) 1-st 行, N第行, 1-st 列, M-第)是摇滚。

最初,玩家休息在广场上 (2,2),这是冰。
玩家可以进行以下动作零次或多次。

  • 首先,指定移动方向:上、下、左或右。
  • 然后,继续朝那个方向移动,直到玩家撞到一块岩石。正式地,继续执行以下操作:
    • 如果移动方向的下一个方格是冰,则前往该方格并继续移动;
    • 如果移动方向的下一个方格是岩石,则留在当前方格并停止移动。

找出玩家可以触摸(通过或停留)的冰块数量。

约束

  • 3 \le N,M \le 200
  • S_i 是一个长度为的字符串 M 组成 # 和 ..
  • 广场 (i, j) 是摇滚如果 i=1, i=N, j=1,或 j=M.
  • 广场 (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
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

示例输出 2

215