Taeyang commence un jeu avec $MN$ pierres blanches et noires disposées sur une grille de $M\times N$, comme ci-dessous.
Pour toute pierre $X$, les $4$ pierres immédiatement au-dessus, au-dessous, à gauche et à droite sont appelées ses voisines. Taeyang peut choisir une pierre et changer sa couleur. Ses voisines qui avaient la même couleur initiale prennent également la nouvelle couleur. Le processus se répète : les voisines des pierres qui changent de couleur changent aussi si elles avaient la même couleur initiale.
Par exemple, changer la pierre $A$ de la figure précédente en blanc rend blanches les pierres noires en forme de « ㄷ », comme ci-dessous.
Changer ensuite la pierre $C$ en blanc donne la figure suivante.
Puis, on change la pierre $F$ en blanc et enfin la pierre $E$ en blanc : toutes les pierres deviennent blanches. Il a donc fallu quatre changements pour rendre toutes les pierres blanches.
Cependant, deux changements suffisent pour que toutes aient la même couleur. Changer d’abord la pierre $B$ en noir donne la figure suivante.
On peut alors changer la pierre $A$ en blanc pour que toutes soient blanches, ou la pierre $D$ en noir pour que toutes soient noires. Ainsi, deux changements suffisent pour uniformiser la couleur.
Écrivez un programme qui, pour des pierres blanches et noires sur une grille de $M\times N$, calcule le nombre minimal de changements de couleur pour que toutes aient la même couleur.
Entrée
La première ligne contient deux entiers strictement positifs $M$ et $N$ décrivant la grille de $M\times N$, séparés par une espace. Ils sont tous deux compris entre $2$ et $100$, bornes incluses. Chacune des $M$ lignes suivantes contient $N$ valeurs séparées par des espaces décrivant une ligne de la grille : $0$ représente une pierre blanche et $1$ une pierre noire.
Sortie
Affichez sur la première ligne le nombre minimal de changements de couleur pour que toutes les pierres aient la même couleur.
Exemples
Entrée 1
5 6 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1
Sortie 1
2