← 返回题目列表

AtCoder · tenka1_2012_8

D. 大爆発

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

問題文

你有一个由方块组成的舞台,你可以玩一个游戏,使用炸弹摧毁该舞台上的所有方块。
炸弹只能放置在没有方块的方格上,放置后会立即爆炸,摧毁顶部、底部、左侧和右侧的所有方块。

例如,图 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) 表示方块处于以下状态。
      • . :表示该方格内没有方块,可以在该方格上放置炸弹。
      • # :表示该方格内有一个方块,不能在该方格上放置炸弹。

部分点

小舞台尺寸的输入 如果只有 (1≤W≤5, 1≤H≤5) 是正确的,100 部分积分换满分 50 点。 如果您正确回答了所有满足

出力

舞台上有积木。 1 消除所有炸弹所需的炸弹数量被发送到标准输出。 输出为 1 行。
另外,如果你无法使舞台上没有方块的状态, -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
  • 由于在给定时间不存在任何方块,因此不需要炸弹。