Optimal Cutting#4649
Polycarp has a rectangular grid consisting of n \times m cells, where each cell contains a lowercase Latin letter.
Two cells are called connected if they share a side and have the same letter written in them.
A monochromatic region is a group of cells such that any two cells in the group are connected (directly or indirectly through a sequence of other cells), and it is not possible to add any more cells to the group without violating this property.
A side of a cell is called internal if it separates two distinct cells of the grid.
A path is a sequence of distinct internal sides, where each pair of consecutive sides meet at a corner of some cell.
Polycarp wants to separate all monochromatic regions from each other by cutting the grid. Each cut may be made along a path—that is, it may cut through a sequence of previously uncut internal sides forming a path. After all cuts, no monochromatic region should be split.
What is the minimum number of cuts Polycarp needs to achieve this?
The first line contains two integers and (1 \leq n \times m \leq 10^5)—the dimensions of the grid.
Each of the next lines contains lowercase Latin letters, describing the grid.
Output a single integer: the minimum number of cuts required to separate all monochromatic regions.
Example 1