Minimum Clue Selection in Crossword Puzzle

This problem is based on the COCI 2019/2020 Contest #6 T4 problem, “Skandi”. In the puzzle a crossword grid of size $N\times M$ is given. Before the game starts, some cells in the grid already contain uppercase letters; these cells serve as starting points (each can start at most two questions) for filling in answers. A starting point gives rise to a horizontal question if its right‐neighbor exists and is blank, and to a vertical question if its bottom neighbor exists and is blank. The answer for a given question is defined to be the maximal contiguous block of blank cells in the given direction (stopping at the grid boundary or just before another pre–filled starting cell).

When a question is answered, all cells in its corresponding word become filled with letters. Note that each blank cell is covered by at most one horizontal question (from the pre–filled cell immediately to its left) and at most one vertical question (from the pre–filled cell immediately above). To complete the crossword, every blank cell must be filled by at least one answered question. Some blank cells are covered by only one question – these clues are forced – while cells covered by both a horizontal and a vertical question create intersections that allow a choice. It can be shown that the task of choosing the minimum number of questions to answer to fill all blank cells is equivalent to selecting a minimum vertex cover on a bipartite graph constructed as follows:

• Let each horizontal (and vertical) question be a vertex in the left (and right) partition respectively.
• For every blank cell that lies in both a horizontal and a vertical word, add an edge connecting the corresponding vertices.

By Kőnig’s theorem the size of a minimum vertex cover equals the size of a maximum matching in the graph. Thus, the final answer is computed as follows:

$$\text{Answer} = \text{(number of horizontal clues with no intersection)} + \text{(number of vertical clues with no intersection)} + \text{(maximum matching size)}.$$

inputFormat

The first line contains two integers $N$ and $M$ ($1\leq N,M\leq 1000$) — the number of rows and columns of the grid. The following $N$ lines each contain a string of length $M$. Each character is either an uppercase letter (A–Z) representing a pre–filled cell (and a valid clue starting point) or a dot ('.') representing a blank cell.

outputFormat

Output a single integer — the minimum number of questions that must be answered in order to fill all blank cells.

sample

3 4
A...
....
B...

3