← 返回题目列表

Codeforces · 1344/B

B. 单极磁铁

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

单极磁铁是一种只有一个极(北极或南极)的磁铁。它们实际上并不存在,因为真正的磁铁有两个磁极,但这是一个编程竞赛问题,所以我们不在乎。

有一个 $$$n\times m$$$ 网格。最初,您可以将一些北极磁铁和一些南极磁铁放入单元格中。您可以放置​​任意数量的磁铁,甚至可以在同一个单元中放置多个磁铁。

执行操作如下。选择要激活的北磁体和南磁体。如果它们位于同一行或同一列并且占据不同的单元格,则北磁体将向南磁体移动一个单位。否则,如果它们占据相同的单元格或不共享行或列,则不会发生任何变化。请注意,南磁体是不可移动的。

网格的每个单元格都是黑色或白色。让我们考虑如何在单元中放置磁铁,以满足以下条件。

1. 每行每列至少有一个南极磁体。
2. 如果某个单元格颜色为黑色,则从初始放置开始经过一系列操作后,北磁体可能会占据该单元格。
3. 如果某个单元格颜色为白色,则从初始放置开始经过一系列操作后,北极磁体不可能占据该单元格。

确定是否可以放置磁铁以满足这些条件。如果可能的话,找出所需的最小北极磁体数量(对南极磁体数量没有要求)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,m\le 1000$$$) — 分别是行数和列数。

接下来的 $$$n$$$ 行描述了颜色。这些行的第 $$$i$$$ 包含长度为 $$$m$$$ 的字符串,其中第 $$$j$$$ 字符表示行 $$$i$$$ 和列 $$$j$$$ 中单元格的颜色。字符“#”和“.”分别代表黑色和白色。可以保证该字符串不会包含任何其他字符。

输出

输出一个整数,即所需的北极磁体的最小可能数量。

如果没有满足所有条件的磁铁放置位置,则打印单个整数 $$$-1$$$。

示例

输入 #1

3 3
.#.
###
##.

输出 #1

1

输入 #2

4 2
##
.#
.#
##

输出 #2

-1

输入 #3

4 5
....#
####.
.###.
.#...

输出 #3

2

输入#4

2 1
.
#

输出#4

-1

输入 #5

3 5
.....
.....
.....

输出 #5

0

注意

在第一个测试中,以下是磁铁放置示例:

在第二个测试中,我们可以证明不存在所需的磁铁放置位置。以下是不符合要求的三个示例展示位置。第一个例子违反了规则$$$3$$$,因为我们可以将北极磁体向下移动到白色方块上。第二个示例违反了规则 $$$2$$$,因为我们无法通过任何操作序列将北极磁体移动到左下角的黑色方块。第三个示例违反了规则 $$$1$$$,因为第一列中没有南极磁体。

在第三个测试中,以下是磁铁的放置示例。我们可以证明,不需要放置具有较少北磁体的磁体。

在第四个测试中,我们可以证明不存在所需的磁铁放置位置。以下是两个不符合要求的示例展示位置。第一个示例违反了规则 $$$1$$$,因为第一行中没有南极磁体。第二个示例违反了 $$$1$$$ 和 $$$3$$$ 规则,因为第二行中没有南极磁体,我们可以将北极磁体向上移动一个单位到白色方块上。

在第五次测试中,我们可以在每个单元中放置南磁体,而不放置北磁体。因为没有黑色单元格,所以这将是正确的位置。