题干：

Leo has a grid with N rows and M columns. All cells are painted with either black or white initially.

Two cells A and B are called connected if they share an edge and they are in the same color, or there exists a cell C connected to both A and B.

Leo wants to paint the grid with the same color. He can make it done in multiple steps. At each step Leo can choose a cell and flip the color (from black to white or from white to black) of all cells connected to it. Leo wants to know the minimum number of steps he needs to make all cells in the same color.

Input

There are multiple test cases. The first line of input contains an integer Tindicating the number of test cases. For each test case:

The first line contains two integers N and M (1 <= N, M <= 40). Then N lines follow. Each line contains a string with N characters. Each character is either 'X' (black) or 'O' (white) indicates the initial color of the cells.

Output

For each test case, output the minimum steps needed to make all cells in the same color.

Sample Input

2
2 2
OX
OX
3 3
XOX
OXO
XOX

Sample Output

1
2

Hint

For the second sample, one optimal solution is:

Step 1. flip (2, 2)

XOX
OOO
XOX

Step 2. flip (1, 2)

XXX
XXX
XXX

题目大意：

字符一样并且相邻的即为连通。每次可翻转一个连通块X(O)的颜色，问至少改变几次使得图上所有字符都相等

解题报告：

思路1：直接枚举起点，然后暴力搜。这个步骤搜的O那下一个步骤就搜X。。

思路2：dfs连通块缩点，枚举起点bfs求最短路，注意要用连通块来求bfs，，不然会T。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 55;
char s[MAX][MAX];
int bk[MAX][MAX];
int nx[4] = {1,0,-1,0};
int ny[4] = {0,1,0,-1};
int tot,n,m;
int vis[MAX*MAX];
vector<int> vv[MAX*MAX];
struct Node {
	int id;
	int t;
	Node(){}
	Node(int id,int t):id(id),t(t){}
};
bool ok(int x,int y) {
	if(x>=1&&x<=n&&y>=1&&y<=m) return 1 ;
	else return 0 ;
}
void dfs(int x,int y,char tar) {
	bk[x][y] = tot;	
	for(int k = 0; k<4; k++) {
		int tx = x + nx[k];
		int ty = y + ny[k];
		if(ok(tx,ty) == 0) continue;
		if(s[tx][ty] == tar) {
			if(bk[tx][ty] == -1) dfs(tx,ty,tar);
		}
		else if(bk[tx][ty] != -1) {
			vv[tot].pb(bk[tx][ty]);
			vv[bk[tx][ty]].pb(tot);
		}
	}
}

int bfs(int x) {
	memset(vis,0,sizeof vis);
	queue<Node> q;
	int res = 0;
	q.push(Node(x,0));
	vis[x]=1;
	while(q.size()) {
		Node cur = q.front();q.pop();
		int col = cur.id;
		
		res = cur.t;
		int up = vv[col].size();
		for(int i = 0; i<up; i++) {
			int v = vv[col][i];
			if(vis[v]) continue;
			vis[v]=1;
			q.push(Node(v,cur.t+1));
		} 
	} 
	return res;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		tot=0;
		memset(bk,-1,sizeof bk);
		scanf("%d%d",&n,&m);
		for(int i = 1; i<=n; i++) {
			scanf("%s",s[i]+1);
		}
		for(int i = 1; i<=n*m; i++) vv[i].clear();
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				if(bk[i][j]== -1) {
					tot++;
					dfs(i,j,s[i][j]);
				}
			}
		}
		int ans = 9999999;
		for(int i = 1; i<=tot; i++) ans = min(ans,bfs(i));
		printf("%d\n",ans);
	}


	return 0 ;
}