Grid Game

Taeyang starts a game with MN white and black stones placed on an M×N grid.

For a stone X, its neighbors are the stones directly adjacent to X above, below, left, and right, up to four stones total. In one color change, Taeyang chooses one stone and changes it to the other color. Every stone that had the same color as the chosen stone before the change and was connected to it through up, down, left, and right adjacencies also changes to the new color. In other words, one move recolors one entire connected monochrome region to the opposite color.

For example, if stone A in the picture above is changed to white, the black stones forming the same C-shaped region as A all become white, producing the following state.

Next, changing stone C to white gives this state.

Then changing stone F to white and finally changing stone E to white makes every stone white. Thus, four color changes are enough to make all stones white.

However, two color changes are sufficient to make all stones the same color. First, changing stone B to black gives the following state.

From there, changing stone A to white makes every stone white, while changing stone D to black makes every stone black. Therefore, the minimum number of moves in this case is two.

Given white and black stones on an M×N grid, find the minimum number of color changes needed to make all stones the same color.

The first line contains two positive integers M and N, the dimensions of the grid. Both M and N are between 2 and 100 inclusive. Each of the next M lines describes one row of the grid with N integers separated by spaces. A white stone is represented by 0, and a black stone is represented by 1.

Print the minimum number of color changes needed to make all stones the same color.