← 返回题目列表

AtCoder · past202010_g

G. 村庄维护

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

分数: 6 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

AtCoder Village被划分为一个矩形网格, N 行向东西方向移动并且 M 列从北向南,总共 N \times M 方块。 有些方块是“墙方块”。如果 S_{i, j} is #,位于 i第行和 j第-列是一个墙方格;如果 S_{i, j} is .,那个方块不是墙方块。 您将恰好将其中一个墙方块更改为非墙方块。 如果更改后必须满足以下条件,请找出您可以选择更改的墙方块的数量:

  • 对于每对两个无墙方格,可以通过重复向上、下、左或右移动一个方格来在这些方格之间移动,仅穿过村庄中的无墙方格。

约束

  • 1 \le N \le 10
  • 1 \le M \le 10
  • N 和 M 是整数。
  • S_i 是一个长度为的字符串 M 组成 # 和 .. (1 \le i \le N)
  • 存在至少一个墙方格和至少一个非墙方格。

输入

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

N M
S_1
S_2
S_3
\hspace{3pt} \vdots
S_N

输出

打印您可以选择更改以满足条件的墙方块数量。


示例输入 1

3 3
..#
#..
.##

示例输出 1

2

例如,如果您更改 2- 从北数第 2 行, 1-从西边到无墙方格的第一列,可以在每对无墙方格之间移动。 您还可以选择位于 3- 从北数第 1 行, 2- 从西数第 2 列满足条件。没有其他这样的墙方格,所以答案是 2.


示例输入 2

3 3
##.
##.
...

示例输出 2

3

除了西北角的墙方格之外,可以选择每个墙方格来满足条件。 请注意,必须可以在每对两个非墙方块之间移动,包括您制作的新非墙方块。