407928: GYM102944 E East Lansing

East Lansing is home to MSU, one of the Michigan Wolverines' greatest rivals (we dare not speak the name Ohio State). Every year at the Michigan-MSU football game, stadium bleachers fill with fans clad in either green t-shirts (one of the MSU colors), or blue t-shirts (one of the Michigan colors), or some other neutral color (why are these people here, anyway?). As you stand on the field staring up an $$$N\times M$$$ grid of seats, you notice that there are some connected regions of green clad fans, some connected regions of blue clad fans, and a few neutrally clad fans interspersed.

You see an opportunity to promote your newly acquired t-shirt company. You decide to "suggest" to some of the neutrally clad people that they commit: you will provide a green or blue t-shirt for them to wear, but you choose the color each person gets. They all agree to wear the shirt you provide because, after all, who doesn't want a free t-shirt? You decide to choose the colors in such a way that the number of connected regions (i.e., the number of green regions plus the number of blue regions) is minimized. You believe this will be a more pleasing arrangement in the advertising photo you plan to take. To clarify: if you can find a way to go from a seat to an adjacent seat in one of the four directions (up, down, right, or left) without changing the color, then these two seats are considered to be in the same connected region; you do not consider diagonally adjacent seats of the same color.

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1\le N, M\le 100$$$). In each of the next $$$N$$$ lines there is a string of length $$$M$$$ consisting of characters '0', '1', and '?'. A '0' character means that the person in this seat is currently wearing green. A '1' character means that the person in this seat is currently wearing blue. A '?' character means that the person in this seat is wearing a neutral color. There will be at most 10 '?' characters in an input file.

Output the minimum number of same color connected regions assuming you made the optimal suggestions (and they were accepted).

3 4
0101
????
0101

4

2 3
111
111

1

3 4
????
?01?
????

2

5 10
0000000011
0111?11111
0111001100
0?1111?000
110000000?

3