問題文
你有一个由方块组成的舞台,你可以玩一个游戏,使用炸弹摧毁该舞台上的所有方块。
炸弹只能放置在没有方块的方格上,放置后会立即爆炸,摧毁顶部、底部、左侧和右侧的所有方块。
例如,图 1 如果你在 (1,3) 上放置炸弹,它会向上、向下、向左、向右移动。 5 你可以摧毁一个方块。
以下坐标指的是舞台左上角的方块。 (0,0) 和1 右边的正方形 (1,0)、1 下面的方块 (0,1) 。
此时,图
就像 1 中炸弹上方的方块一样,即使炸弹和方块不相邻也会被摧毁,而且无论连续有多少个方块,所有方块都会被摧毁。
另外,就像炸弹右侧的方块一样,所有方块即使不相邻也会被摧毁。
図 1 :炸弹摧毁方块的示例
回答摧毁舞台上所有方块所需的炸弹数量。
另外,如果不可能摧毁所有方块, -1 。
入力
H W
c_{(0,0)}c_{(1,0)}‥‥c_{(W-1,0)}
c_{(0,1)}c_{(1,1)}‥‥c_{(W-1,1)}
:
:
c_{(0,H-1)}c_{(1,H-1)}‥‥c_{(W-1,H-1)}
- 输入是 H+1 。
- 1 行包含一个整数,表示给定阶段的垂直长度。 H(1≤H≤16) 和代表宽度的整数 W(1≤W≤16) 作为空格分隔符给出。
- 2 从线 H 行中,每行指示阶段的每个方格是否存在块。 c_{(i,j)}(0≤i≤W-1, 0≤j≤H−1) 是
在 W 逐个字符给出。
- c_{(i,j)} 是以下之一,坐标是 (i,j) 表示方块处于以下状态。
.:表示该方格内没有方块,可以在该方格上放置炸弹。#:表示该方格内有一个方块,不能在该方格上放置炸弹。
- c_{(i,j)} 是以下之一,坐标是 (i,j) 表示方块处于以下状态。
部分点
出力
另外,如果你无法使舞台上没有方块的状态,
-1 。
在第请注意,行尾需要换行。 定义
入力例 1
5 5 .#.#. .#... ...#. #.#.# #...#
出力例 1
2
- 初始位置如图所示。 由于 1 是所示的形式,首先是坐标 如果你在 (1,3) 坐标处放置炸弹 你可以摧毁 (0,3), (1,0), (1,1), (2,3), (4,3) 块。
- 然后是坐标 通过在 (3,4) 位置放置炸弹,您可以摧毁所有剩余的方块。
- 因此,摧毁所有方块所需的炸弹数量为 2 件。
入力例 2
5 5 .#... .#... ##### .#... .#...
出力例 2
3
- 一、坐标 在 (0,1) 上放置炸弹 摧毁(0,2) 和 按字典顺序比较 (1,1) 块。
- 接下来,坐标 (1,1) 上放置炸弹 摧毁(1,0), (1,2), (1,3), (1,4) 块。
- 最后是坐标 通过在 (1,2) 上放置炸弹,你可以摧毁所有剩余的方块。
- 因此,摧毁所有方块所需的炸弹数量为 3 件。
入力例 3
1 6 ######
出力例 3
-1
- 方块无法被摧毁,因为炸弹无法放置在任何方格上。
入力例 4
3 2 .. .. ..
出力例 4
0
- 由于在给定时间不存在任何方块,因此不需要炸弹。