文理学院程序设计在线练习


Cake Cutting Problem

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

Alice and Bob are good friends,but their preferences for cakes are pretty different.
Now the baker has made a piece of N*M cake with both chocolate and cream. Alice prefers cream but bob prefers chocolate. In order to make both of them happy, the baker decided to divide the cake into pieces that completely separate chocolate and cream, in other words, each piece is either chocolate or cream. Each operation the baker will choose a piece of cake (this cake could be created by the previous operation,one cut can’t operate on multiple pieces) and cut it along one of the vertical or horizontal axes. The bake wants to know the least cut he can be used to completely split the cake.

Input

Input contains an Integer T in the first line, represents the number of cases.
For each case, the first line contains two Integers N, M, represents the size of cake. Following N lines, each line contains a string with M characters, represents the details of cake.
‘x’ means chocolate, and ‘o’ means cream.
Limit:
T <= 10
N, M <= 40

Output

For each case output one line contains an Integer represents the least cut.

Sample Input
1
4 4
xxoo
xxoo
xooo
xoxx
Sample Output
4
Hint

xxoo x|xoo x|x|oo x|x|oo x|x|oo
xxoo x|xoo x|x|oo x|x|oo x|x|oo
xooo => x|ooo => x|o|oo => x|-|oo => x|-|oo
xoxx x|oxx x|o|xx x|o|xx x|o|--
o o|xx

the ‘-’ and ‘|’ represent the position of cut. Total 4 cuts.

Source

2019绍兴市计算机技能竞赛