本题分为读入 dfs灌水求连通块 在相邻连通块之间连边建图 以每个连通块为起点跑bfs求最短路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=75,NN=4905;
int n,m,col[N][N],cool[NN],w[NN],id[N][N],xx,yy,xxx,yyy,cnt=0/*连通块个数*/,dis[NN],ans=1e9,d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
char c;
bool vvis[NN],vis[N][N],vis_of_block[NN][NN];
vector<int > adj[NN];
void dfs(int x,int y){
    if(vis[x][y])return;
    vis[x][y]=1;
    id[x][y]=cnt;
    for(int i=0;i<4;i++){
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m/*记得判越界*/&&!vis[xx][yy]&&col[xx][yy]==col[x][y])//属于同一个连通块
            dfs(xx,yy);
    }
}
void bfs(int node){//求图上距离该点最远的点的距离
    memset(vvis,0,sizeof(vvis));
    memset(dis,0,sizeof(dis));
    queue<int > q;
    q.push(node);
    dis[node]=0;
    vvis[node]=1;
    while(!q.empty()){
        int nnd=q.front();
        q.pop();
        for(int i=0;i<adj[nnd].size();i++){
            int nd=adj[nnd][i];
            if(!vvis[nd]){
                vvis[nd]=1;
                dis[nd]=dis[nnd]+1;
                q.push(nd);
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='W')col[i][j]=0;
            else
                col[i][j]=1;
        }
    //return 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(!vis[i][j]){
                id[i][j]=++cnt;
                if(col[i][j]==1)w[cnt]=1;
                cool[cnt]=col[i][j];
                dfs(i,j);
            }
        }

    for(int i=1;i<=n;i++){//相邻连通块之间连边
        for(int j=1;j<=m;j++){
            for(int k=0;k<4;k++){
                int xx=i+d[k][0],yy=j+d[k][1];
                if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&/*注意判断越界*/col[xx][yy]!=col[i][j]){//位于连通块交界处
                    if(!vis_of_block[id[xx][yy]][id[i][j]]){
                        adj[id[xx][yy]].push_back(id[i][j]);
                        vis_of_block[id[xx][yy]][id[i][j]]=1;
                    }
                    //adj[id[i][j]].push_back(id[xx][yy]); //啥??这题卡常,建单向边
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        bfs(i);
        int aans=-1e9;
        for(int k=1;k<=cnt;k++){
            aans=max(aans,dis[k]+w[k]); 
        }
        ans=min(ans,aans);
    }
    printf("%d\n",ans);
    return 0;
}