CF1344B.Monopole Magnets

A monopole magnet is a magnet that only has one pole, either north or south. They don't actually exist since real magnets have two poles, but this is a programming contest problem, so we don't care.

There is an $n\times m$ grid. Initially, you may place some north magnets and some south magnets into the cells. You are allowed to place as many magnets as you like, even multiple in the same cell.

An operation is performed as follows. Choose a north magnet and a south magnet to activate. If they are in the same row or the same column and they occupy different cells, then the north magnet moves one unit closer to the south magnet. Otherwise, if they occupy the same cell or do not share a row or column, then nothing changes. Note that the south magnets are immovable.

Each cell of the grid is colored black or white. Let's consider ways to place magnets in the cells so that the following conditions are met.

1. There is at least one south magnet in every row and every column.
2. If a cell is colored black, then it is possible for a north magnet to occupy this cell after some sequence of operations from the initial placement.
3. If a cell is colored white, then it is impossible for a north magnet to occupy this cell after some sequence of operations from the initial placement.

Determine if it is possible to place magnets such that these conditions are met. If it is possible, find the minimum number of north magnets required (there are no requirements on the number of south magnets).

磁单极子是一种仅具有一个磁极（北极或南极）的磁体。实际上它们并不存在，因为真实磁体总是同时具有两个磁极；但这是一个编程竞赛题目，因此我们并不在意这一点。

给定一个 $n\times m$ 的网格。初始时，你可以在某些格子中放置若干个北极磁体和若干个南极磁体。你可以任意放置磁体（包括在同一个格子中放置多个磁体）。

一次操作定义如下：选择一个北极磁体和一个南极磁体进行激活。若它们位于同一行或同一列，且占据不同的格子，则该北极磁体向该南极磁体方向移动一格（即行号或列号更接近南极磁体）；否则（即二者位于同一格子，或既不同行也不同列），则不发生任何变化。注意：南极磁体是不可移动的。

网格中每个格子被染成黑色或白色。现考虑在格子中放置磁体的方式，使得满足以下条件：

1. 每一行和每一列中都至少存在一个南极磁体；
2. 若某个格子被染成黑色，则从初始磁体布局出发，经过若干次操作后，可能使某个北极磁体占据该格子；
3. 若某个格子被染成白色，则从初始磁体布局出发，经过任意次操作后，都不可能使任何北极磁体占据该格子。

请判断是否存在满足上述条件的磁体放置方式。若存在，请找出所需北极磁体的最小数量（对南极磁体的数量无任何限制）。

The first line contains two integers $n$ and $m$ ($1\le n,m\le 1000$) — the number of rows and the number of columns, respectively.

The next $n$ lines describe the coloring. The $i$-th of these lines contains a string of length $m$, where the $j$-th character denotes the color of the cell in row $i$ and column $j$. The characters "#" and "." represent black and white, respectively. It is guaranteed, that the string will not contain any other characters.

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 1000$），分别表示行数和列数。

接下来的 $n$ 行描述了着色情况。其中第 $i$ 行是一个长度为 $m$ 的字符串，该字符串中第 $j$ 个字符表示第 $i$ 行第 $j$ 列单元格的颜色。“#” 和 “.” 分别代表黑色和白色。保证该字符串不包含其他任何字符。

Output a single integer, the minimum possible number of north magnets required.

If there is no placement of magnets that satisfies all conditions, print a single integer $-1$.

输出一个整数，表示所需北磁极的最小数量。

如果不存在满足所有条件的磁极放置方案，则输出整数 $-1$。

In the first test, here is an example placement of magnets:

In the second test, we can show that no required placement of magnets exists. Here are three example placements that fail to meet the requirements. The first example violates rule $3$ since we can move the north magnet down onto a white square. The second example violates rule $2$ since we cannot move the north magnet to the bottom-left black square by any sequence of operations. The third example violates rule $1$ since there is no south magnet in the first column.

In the third test, here is an example placement of magnets. We can show that there is no required placement of magnets with fewer north magnets.

In the fourth test, we can show that no required placement of magnets exists. Here are two example placements that fail to meet the requirements. The first example violates rule $1$ since there is no south magnet in the first row. The second example violates rules $1$ and $3$ since there is no south magnet in the second row and we can move the north magnet up one unit onto a white square.

In the fifth test, we can put the south magnet in each cell and no north magnets. Because there are no black cells, it will be a correct placement.

在第一个测试中，以下是一个磁铁放置的示例：

在第二个测试中，我们可以证明不存在满足要求的磁铁放置方案。以下是三个不满足要求的示例放置方案：第一个示例违反规则 $3$，因为我们可以将北极磁铁向下移动至一个白色方格；第二个示例违反规则 $2$，因为我们无法通过任何操作序列将北极磁铁移动至左下角的黑色方格；第三个示例违反规则 $1$，因为在第一列中没有南极磁铁。

在第三个测试中，以下是一个磁铁放置的示例。我们可以证明：不存在使用更少北极磁铁的满足要求的磁铁放置方案。

在第四个测试中，我们可以证明不存在满足要求的磁铁放置方案。以下是两个不满足要求的示例放置方案：第一个示例违反规则 $1$，因为在第一行中没有南极磁铁；第二个示例同时违反规则 $1$ 和规则 $3$，因为在第二行中没有南极磁铁，且我们可以将北极磁铁向上移动一格至一个白色方格。

在第五个测试中，我们可以在每个单元格中放置一个南极磁铁，且不放置任何北极磁铁。由于该网格中不存在黑色方格，因此这是一种正确的放置方案。