题目大意
给你个矩形的图，里面只有X和O你现在要把整个图全部翻成X或全部成O，翻的规则为，你如果翻一个X那么跟它连通的X都会被翻过来。翻O同理。问你需要翻几次。
样例输入
2
2 2
OX
OX
3 3
XOX
OXO
XOX
样例输出
1
2
分析
就先把每个连通的部分找出来并从1开始编号。然后将相邻的连通块之间构建一条边。再用这个邻接表来进行bfs。
对自己PS：对邻接表bfs时可以用vis记录点是否被访问，然后访问所有点，用一个ans来保持步数最大。
代码如下：
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
int num[50][50];
char mapn[50][50];
int dx[5] = {0,1,0,-1};
int dy[5] = {1,0,-1,0};
vector<int> g[1610];
int vis[1610];
int n,m;
struct node{
int step,id;
};
void dfs(int x,int y,int con ,char c){
for(int i = 0 ; i < 4 ; i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if(mapn[xx][yy] == c){
if(num[xx][yy] == -1){
num[xx][yy] = con;
dfs(xx,yy,con,c);
}
}
else{
if(num[xx][yy] != -1){
int tmp = num[xx][yy];
//printf("x = %d , y = %d || xx = %d , yy = %d \n",x,y,xx,yy);
g[tmp].push_back(con);
g[con].push_back(tmp);
}
}
}
}
int bfs(int x)
{
queue<node>q;
node str,now,tmp;
str.id = x;
str.step = 0;
vis[x] = 1;
q.push(str);
int ans = 0;
while(!q.empty())
{
now = q.front();
q.pop();
if(ans < now.step) ans = now.step;
for(int i = 0 ; i < g[now.id].size() ; i++){
int tx = g[now.id][i];
if(vis[tx] != 1){
tmp.id = tx;
tmp.step = now.step+1;
vis[tx] = 1;
q.push(tmp);
}
}
}
return ans;
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--){
CLR(mapn);
scanf("%d%d",&n,&m);
for(int i = 0 ; i < n ; i++){
scanf("%s",mapn[i]);
}
CLR(g);
memset(num,-1,sizeof(num));
int cnt = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(num[i][j] == -1){
cnt++;
num[i][j] = cnt;
dfs(i,j,cnt,mapn[i][j]);
}
}
}
/*
printf(" num : \n");
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
printf("%d ",num[i][j]);
}
printf("\n");
}
printf("\n");
printf(" vector : \n");
for(int i = 1 ; i <= cnt ; i++){
printf("%d ---> ",i);
for(int j = 0 ; j < g[i].size() ; j++){
printf("%d ",g[i][j]);
}
printf("\n");
} */
int ans = inf;
for(int i = 1 ; i <= cnt ; i++){
CLR(vis);
ans = min(ans,bfs(i));
}
printf("%d\n",ans);
}
}
