그리드 게임

태양이는 M×N 그리드 위에 놓인 MN개의 흰색 돌과 검은색 돌로 게임을 시작한다.

어떤 돌 X에 대해, X와 상하좌우로 인접한 최대 네 개의 돌을 X의 이웃이라고 하자. 한 번의 색 바꾸기에서는 돌 하나를 골라 그 색을 다른 색으로 바꾼다. 이때 선택한 돌이 바뀌기 전과 같은 색이었고, 상하좌우 인접 관계로 선택한 돌과 연결되어 있던 모든 돌도 함께 새 색으로 바뀐다. 다시 말해, 한 번의 색 바꾸기는 같은 색으로 연결된 하나의 영역 전체를 반대 색으로 바꾸는 동작이다.

예를 들어 위 그림에서 돌 A의 색을 흰색으로 바꾸면, A와 같은 검은색 영역을 이루던 'ㄷ'자 모양의 돌들이 모두 흰색으로 바뀌어 다음과 같은 상태가 된다.

이어서 돌 C를 흰색으로 바꾸면 다음과 같이 된다.

그 뒤 돌 F를 흰색으로 바꾸고, 마지막으로 돌 E를 흰색으로 바꾸면 모든 돌이 흰색이 된다. 따라서 네 번의 색 바꾸기로 모든 돌을 흰색으로 만들 수 있다.

하지만 두 번만으로도 모든 돌을 같은 색으로 만들 수 있다. 먼저 돌 B를 검은색으로 바꾸면 다음과 같은 상태가 된다.

이제 돌 A를 흰색으로 바꾸면 모든 돌이 흰색이 되고, 돌 D를 검은색으로 바꾸면 모든 돌이 검은색이 된다. 따라서 이 경우의 최소 횟수는 두 번이다.

흰색과 검은색 돌들이 M×N 그리드 위에 놓여 있을 때, 모든 돌이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 구하시오.

첫째 줄에 그리드의 크기를 나타내는 두 양의 정수 M과 N이 공백으로 구분되어 주어진다. M과 N은 각각 2 이상 100 이하이다. 둘째 줄부터 M개의 줄에는 각 가로줄에 놓인 돌의 색이 주어진다. 흰색 돌은 0, 검은색 돌은 1로 나타내며, 각 줄마다 N개의 정수가 공백으로 구분되어 주어진다.

모든 돌이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 첫째 줄에 출력한다.