PROBLEM STATEMENT

You just designed a single-player game called the Flipping Game.



The game is played on a rectangular board that is divided into n rows by m columns. 
The game is played using square tiles. 
The tiles have the same size as the unit square cells on the board. 
Each tile has one side white and the other side black.



You are given n, m, and a vector <string> X that represents the initial state of the board. 
More precisely, the character X[r][c] represents the cell in row r, column c of the board: 
'w' means that this cell contains a tile that is white (i.e., white on top, black on bottom), 'b' 
is a black tile, and 'e' is an empty cell without a tile.



The game is played in turns. 
Each turn looks as follows: 
Choose any tile T, note its color C, and flip the tile T to show the opposite color. 
Then, the flip cascades: whenever you flip some tile X and there is a tile Y adjacent to X such 
that the color of Y is also C, you have to flip Y as well. 
Two tiles are considered adjacent if they share a side. 
The turn ends when the cascade ends and there are no more tiles you have to flip.



You win the game when all tiles on the board show the same color. 
Determine and return the smallest number of turns needed to win the game. 
Note that it is always possible to win the game.



DEFINITION
Class:TileFlippingGame
Method:HowManyMoves
Parameters:int, int, vector <string>
Returns:int
Method signature:int HowManyMoves(int n, int m, vector <string> X)


CONSTRAINTS
-n will be between 2 and 20, inclusive.
-m will be between 2 and 20, inclusive.
-X will contain exactly n elements.
-Each element of X will contain exactly m elements.
-Each element of each element of X will be one of 'e', 'b', and 'w'.
-If we concatenate all elements of X, it will contain at least one 'e', at least one 'b', and at 
least one 'w'.


EXAMPLES

0)
3
3
{"bbb","eee","www"}

Returns: 1

Regardless of which tile you choose to flip, the game ends after the first turn.


1)
3
3
{"bwe","wbw","ewb"}

Returns: 2

First, flip the black tile at the center of the board to white.
Then flip any of the five white tiles to turn all seven tiles to black side up.


2)
4
4
{"beww","beww","beww","wewe"}

Returns: 1



3)
2
8
{"ewewbbbb","bwebewww"}

Returns: 3



4)
5
5
{"bwebw","wbebb","eeeee","bbebb","bbebb"}

Returns: 3

Initially the board looks as follows:


bwebw
wbebb
eeeee
bbebb
bbebb


There are three white tiles. 
One optimal solution is to flip these three tiles from white to black (one tile per turn).
There are also other optimal solutions.
For example, you can start by flipping the top left tile from black to white.

The best way to make all the tiles white requires five flips, which is stricty worse.

5)
6
7
{"bwbbbbb","bwbwwwb","bwbwewb","bwbbbwb","bwwwwwb","bbbbbbb"}

Returns: 1

Initially, the game board looks like the following:

bwbbbbb
bwbwwwb
bwbwewb
bwbbbwb
bwwwwwb
bbbbbbb

As soon as we flip any tile (whether black or white), the game ends.

6)
6
7
{"bwbbbbb","bwbwwwb","eeeeeee","bwbbbwb","bwwwwwb","bbbbbbb"}

Returns: 3

The game board looks similar to the one in Example 5, except row 3 is now completely empty (the 
entire row's tiles are missing).

bwbbbbb
bwbwwwb
eeeeeee
bwbbbwb
bwwwwwb
bbbbbbb


In two turns, we can turn the first two rows of tiles to either black or white side up.

For the bottom three rows, in one turn we can flip one of the white tiles to have all of them 
black side up.

Overall in three turns we can flip all tiles to their black side up.


 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.