学步园

题意：给出n*m的只包含‘X’或‘O’的矩阵，可以将一个联通块内所有相连的X翻转成O，也可以将相连的O翻转成X，（相连指有一边相连）问翻转到同一种字符的最少次数

将联通块缩点，然后到别的联通块的距离就是翻转到该联通块需要的次数，对以每个联通块为起点跑一次最短路，求出最长距离，然后在最长距离里面找最短的就行了

/*************************************************************************
    > File Name: a.cpp
    > Author: zzx
    > Mail: 1640787991@qq.com 
    > Created Time: 2015年03月11日 星期三 21时09分13秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 45;

char a[N][N];
int mat[N][N];
bool vis[N][N];
int c[N*N];
int n, m;
int cnt;
int dir[4][2] = {
	1, 0, -1, 0, 0, 1, 0, -1
};
int usd[N * N];
int dis[N*N];

struct edge{
	int v, nxt, w;
}e[N*N*N*N];
int head[N*N];
int k;

queue <int> q;

void init()
{
	memset( vis, 0, sizeof ( vis ) );
	memset( mat, 0, sizeof ( mat ) );
	memset( c, 0, sizeof( c ) );
	k = 0;
	memset( head, -1, sizeof( head ) );
}

void add( int u, int v, int w )
{
	e[k].v = v;
	e[k].w = w;
	e[k].nxt = head[u];
	head[u] = k++;

	e[k].v = u;
	e[k].w = w;
	e[k].nxt = head[v];
	head[v] = k++;
}

void dfs( int x, int y, char col )
{
	for( int i = 0; i < 4; ++i )
	{
		int xx = x + dir[i][0];
		int yy = y + dir[i][1];
		if( vis[xx][yy] && a[xx][yy] != col )
		{
			add( mat[xx][yy], mat[x][y], 1 );
			//printf("u: %d v: %d\n", mat[x][y], mat[xx][yy] );
			continue;
		}
		if( !vis[xx][yy] && xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == col )
		{
			vis[xx][yy] = 1;
			mat[xx][yy] = cnt;
			dfs( xx, yy, col );
		}
	}
}

int spfa( int x, int y )
{
	int st = mat[x][y];
	memset( usd, 0, sizeof( usd ) );
	memset( dis, inf, sizeof( dis ) );
	while( !q.empty( ) )
		q.pop();
	dis[ st ] = 0;
	usd[ st ] = 1;
	int res = -1;
	q.push(st);
	while( !q.empty( ) )
	{
		int u = q.front();
		q.pop();
		usd[u] = 0;
		for( int i = head[u]; ~i; i = e[i].nxt )
		{
			int v = e[i].v;
			//printf("u: %d v: %d\n", u, v);
			if( dis[v] > dis[u] + e[i].w )
			{
				dis[v] = dis[u] + e[i].w;
				if( !usd[v] )
				{
					usd[v] = 1;
					q.push( v );
				}
			}
		}
	}
	for( int i = 1; i <= n*m; ++i )
		if( dis[i] != inf && i != st )
			res = max( res, dis[i] );
	//printf("res: %d\n", res);
	return res;
}

int main()
{
	int tot;
	scanf("%d", &tot);
	while( tot-- )
	{
		init();
		cnt = 0;
		scanf("%d%d", &n, &m);
		for( int i = 1; i <= n; i++ )
			scanf("%s", a[i] + 1);
		for( int i = 1; i <= n; i++ )
		{
			for( int j = 1; j <= m; ++j )
			{
				if( !vis[i][j] )
				{
					vis[i][j] = 1;
					mat[i][j] = ++cnt;
					char col = a[i][j];
					dfs( i, j, col );
				}
			}
		}
		if( cnt == 1 )
		{
			puts("0");
			continue;
		}
		else if( cnt == 2 )
		{
			puts("1");
			continue;
		}
		/*
		for( int i = 1; i <= n; ++i )
		{
			for( int j = 1; j <= m; ++j )
				printf("%d ", mat[i][j]);
			puts("");
		}
		*/
		int ans = inf;
		for( int i = 1; i <= n; ++i )
		{
			for( int j = 1; j <= m; ++j )
			{
				if( !c[ mat[i][j] ] )
				{
					c[ mat[i][j] ] = 1;
					ans = min( ans, spfa( i, j ) );
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

/*
2
3 6
OOXOOX
XOXOOX
XXOXOO
2
*/