BLOCK_D  BLOCK_D SOLVER
You are given a board of order mxn full of coloured blocks.
At each move, you have to select a block of any colour which has atleast one of it's immediate neighbours of same colour. If you select a block, all the connected blocks(not just the immediate neighbours) of same colour gets destroyed. A block is connected to all the blocks that share an edge with it. Any block will fall directly down if there is no block immediately below it. If a complete column becomes empty, you must either push all the columns to it's left once in the right side or push all the columns to it's right once in the left side(These pushes are not considered as a moves. At each move, you will destroy more than one block).
You will win the game if the remaining number of blocks becomes zero after making the moves. Find the minimum number of moves to win the game. If it is impossible to win the game, print 1.
For better understanding of gameplay you may have a look at this video. (optional)
Input:
The first line consists of an integer t, the number of test cases. For each test case the first line consists of two integers m, n the number of rows and columns respectively followed by the matrix representing the coloured blocks. Colour[i][j] contains any character between 'a' and 'e' inclusive.
Output:
For each test case print the minimum number of moves to win the game. If it is impossible to win, print 1.
Input Constraints:
1<=t<=10
1<=m,n<=8
'a'<=Colour[i][j]<='e'
Sample Input:
2
5 5
aaaba
aaaba
aaaba
aaaba
aaaba
5 5
bbbbb
baabb
bbbab
bbbaa
aabab
Sample Output:
2
3
hide comments
David:
20211114 01:03:57
Awesome problem! 

Jacob Plachta:
20160108 15:14:51
Hmm, the grid can actually be up to 10x10, not 8x8 

:D:
20150425 16:44:15
Note that test cases seem to allow a "straight forward" method. You don't have to take into account pessimistic cases. 

Arianto Wibowo:
20150207 04:17:17
The video is private :(

Added by:  cegprakash 
Date:  20130224 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: BF GOSU 