做题感悟：比赛时最后一个多小时就不淡定了，看哪个哪个不会，处于不断切题状态，那时应该找一个做出来几率大的题思考。
题意：这题就两种颜色，颜色相同且有公共边的（或者通过另一个相同的颜色连接）为一个连通块，如果翻转其中一个，与它在同一个连通块里的都要改变颜色，求达到相同颜色的最小步数。
解题思路：dfs ( 建图) + bfs ( 寻找最优解 ) .
1) dfs( 建图 ) ,因为翻转的时候每翻转连通块中一个整个连通块都翻转，这样你可以将其看成一个有边相连的无向图，每个边的两个顶点颜色都不一样。
转化=======〉
2) bfs( 寻找最优解 ) , 建完图后就需要翻转计算最优解，可以枚举从每一点开始翻转所得到的最小步数，那怎样寻找最小步数 ？ 假如从 v 这个顶点出发，那么与 v 相邻的顶点颜色必定都与 v 相反，so~> 你只需要把 v的颜色翻转，v与它相邻的所有顶点都是同一个颜色，这时可以把这些顶点看成一个连通块（顶点），再向四周扩展，再次扩展时，周围的颜色必定与此连通块颜色相反，再将它变成与周围顶点相同的颜色，这样又合并成为一个连通块……这样一直进行下去取最大步数。最后从最大步数中取出最小的步数即为最优解。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
const double PI = 3.1415926 ;
const double esp = 1e-4 ;
const int md= 2810778 ;
const int INF = 999999999 ;
const int MX = 1625 ;
int n,m ;
char s[50][50] ;
int dx[5]={1,-1,0,0},dy[5]={0,0,1,-1} ;
int num[50][50] ; // 用于标记属于哪个集合
bool vis[MX] ;
vector<int>G[MX] ;
struct node
{
int x,step ;
} ;
int bfs(int x)
{
int time=0 ;
queue<node>q ;
node curt,next ;
memset(vis,false,sizeof(vis)) ;
curt.x=x ;
curt.step=0 ;
vis[x]=true ;
q.push(curt) ;
while(!q.empty())
{
curt=q.front() ;
q.pop() ;
if(time<curt.step)
time=curt.step ;
int nx=G[curt.x].size() ;
next.step=curt.step+1 ;
for(int i=0 ;i<nx ;i++)
{
next.x=G[curt.x][i] ;
if(!vis[next.x])
{
vis[next.x]=true ;
q.push(next) ;
}
}
}
return time ;
}
bool search(int x,int y)
{
if(x<0||y<0||x>=n||y>=m)
return false ;
return true ;
}
void dfs(int x,int y,int ct,char ch)
{
for(int i=0 ;i<4 ;i++)
{
int sx=x+dx[i] ;
int sy=y+dy[i] ;
if(search(sx,sy))
{
if(s[sx][sy]==ch)
{
if(num[sx][sy]==-1)
{
num[sx][sy]=ct ;
dfs(sx,sy,ct,ch) ;
}
}
else if(num[sx][sy]!=-1)
{
int temp=num[sx][sy] ;
G[ct].push_back(temp) ; // 建双向边
G[temp].push_back(ct) ;
}
}
}
}
void init() // 初始化
{
memset(num,-1,sizeof(num)) ;
for(int i=0 ;i<n*m ;i++)
G[i].clear() ;
}
int main()
{
int Tx,cnt ;
scanf("%d",&Tx) ;
while(Tx--)
{
scanf("%d%d",&n,&m) ;
init() ;
cnt=0 ;
for(int i=0 ;i<n ;i++)
scanf("%s",s[i]) ;
for(int i=0 ;i<n ;i++)
for(int j=0 ;j<m ;j++)
if(num[i][j]==-1) // 如果没访问过
{
num[i][j]=cnt++ ;
dfs(i,j,cnt-1,s[i][j]) ;
}
int ans=INF ;
for(int i=0 ;i<cnt ;i++) // 广搜寻找最优解
{
int mx=bfs(i) ;
ans=ans > mx ? mx : ans ;
}
printf("%d\n",ans) ;
}
return 0 ;
}