分数: 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