← 返回题目列表

AtCoder · kupc2016_e

E. 栅栏

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

分数: 150 点

问题陈述

网格上有一些山羊, H 行和 W 列。 爱丽丝想在一些不存在山羊的单元格设置一些栅栏,这样任何山羊都无法走出栅栏。 山羊可以向上、下、右、左四个方向移动。 山羊不能移动到有栅栏的牢房上。 如果山羊存在于网格最外面的单元格之一,它可以移动到外面。 在所有栅栏都放置好之前,山羊不会移动。 找出要放置的最少栅栏数量。

约束

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 给定网格上至少有一只山羊。

输入

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

H W
S_1
:
S_H

的 j-th (1 \leq j \leq W) 中的字符 S_i (1 \leq i \leq H) 代表 位于行的单元格中是否存在山羊 i 和专栏 j。 性格 . 代表没有山羊,并且 X 代表牢房里有一只山羊。

输出

打印要放置的栅栏的最小数量。如果无法将所有山羊保留在网格内,请打印 -1.


示例输入 1

4 5
.....
.....
..X..
.....

示例输出 1

4

最佳答案是在位于以下位置的单元格上设置围栏 行 3 和专栏 2, 行 2 和专栏 3, 行 3 和专栏 4, 和行 4 和专栏 3.

示例输入 2

2 2
..
.X

示例输出 2

-1

在这种情况下,没有办法将山羊保留在网格内。

示例输入 3

6 6
......
......
..X...
.X..X.
..X...
......

示例输出 3

10