“小马智行杯“第十九届广东省大学生程序设计竞赛 暨中国大学生程序设计大赛广东省赛 E 黑白大陆

题目链接：https://pintia.cn/problem-sets/1534086341544497152/problems/1534088931057451012

未过，仅存档

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1e10
#define N 200010int n,m,ans=INF,bloc;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dis[2550],mp[55][55],col[2550],ty[2550];
vector<int>g[2550];
struct node
{int x,w;
};
bool operator < (node a,node b)
{return a.w>b.w;
}
void dfs(int x,int y)
{col[(x-1)*m+y]=bloc;for (int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if (nx<1||ny<1||nx>n||ny>m||col[(nx-1)*m+ny])continue;if (mp[x][y]!=mp[nx][ny]) continue;dfs(nx,ny);}
}void dij(int u)
{int xx=u;for (int i=1;i<=bloc;i++) dis[i]=INF;dis[u]=0;priority_queue<node>q;q.push({u,0});while (!q.empty()){node tmp=q.top();q.pop();u=tmp.x;for (int i=0;i<g[u].size();i++){int ne=g[u][i];if (dis[ne]>dis[u]+1){dis[ne]=dis[u]+1;q.push({ne,dis[ne]});}}}int tmp=0,id;for (int i=1;i<=bloc;i++){if (dis[i]>tmp||(dis[i]==tmp && ty[i]==0)){tmp=dis[i];id=i;}// tmp=max(tmp,dis[i]);}if (ty[id]==1 && ty[xx]==1) tmp++;ans=min(ans,tmp);
}
signed main()
{cin>>n>>m;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)cin>>mp[i][j];for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){if (!col[(i-1)*m+j]){++bloc;ty[bloc]=mp[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 nx=i+dx[k],ny=j+dy[k];int xx=col[(i-1)*m+j],yy=col[(nx-1)*m+ny];if (xx!=yy) {g[xx].push_back(yy);// g[yy].push_back(xx);}}// cout<<bloc<<endl;for (int i=1;i<=bloc;i++)dij(i);cout<<ans<<endl;
}