CF37E Trial for Chief（最短路）

题意

题意是给你一张 NMNMNM 的图，每个点有黑色和白色，初始全为白色，每次可以把一个相同颜色的连续区域染色，求最少的染色次数；（n,m<=50)

题解

转化为最短路。对于每一个点与它相邻的相同颜色的点连权值为0的边，对于颜色不同的点连权值为1的点。从每一个点跑单源最短路，把到W点的距离和到B点的距离+1取min作为此点的答案，最后把每一个点的答案取max就是答案。

对于能直接到达的两个颜色相同的点显然只用涂一次，如果不同就要再涂一次，所以这样建图。为了特判全是黑色的情况，所以到B点的距离要加一。显然，这样对于其他情况没有影响。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int INF=0x3f3f3f3f;

 int n,m;

 char s[][];

 int ans=INF;

 int dis[],vis[],head[],cnt;

 struct edge{

     int to,nxt,w;

 }e[];

 void add(int u,int v,int w){

     cnt++;

     e[cnt].nxt=head[u];

     e[cnt].to=v;

     e[cnt].w=w;

     head[u]=cnt;

 }

 int zb(int x,int y){

     return (x-)*m+y;

 }

 void spfa(int ss){

     queue<int> q;

     memset(dis,0x3f,sizeof(dis));

     dis[ss]=;

     q.push(ss);

     vis[ss]=;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         vis[u]=;

         for(int i=head[u];i;i=e[i].nxt){

             int v=e[i].to;

             if(dis[v]>dis[u]+e[i].w){

                 dis[v]=dis[u]+e[i].w;

                 if(vis[v]==){

                     vis[v]=;

                     q.push(v);

                 }

             }

         }

     }

     int tmp=-;

     for(int i=;i<=n*m;i++){

         if(s[(i-)/m+][(i-)%m+]=='B')tmp=max(tmp,dis[i]+);

         else tmp=max(tmp,dis[i]);

     }

     ans=min(ans,tmp);

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++){

             cin>>s[i][j];

         }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++){

             if(i>)add(zb(i,j),zb(i-,j),(s[i][j]!=s[i-][j]));

             if(i<n)add(zb(i,j),zb(i+,j),(s[i][j]!=s[i+][j]));

             if(j>)add(zb(i,j),zb(i,j-),(s[i][j]!=s[i][j-]));

             if(j<m)add(zb(i,j),zb(i,j+),(s[i][j]!=s[i][j+]));

         }

     for(int i=;i<=n*m;i++){

         spfa(i);

     }

     printf("%d",ans);

     return ;

 }

巴特西

CF37E Trial for Chief（最短路）

题意

题解

最新文章

热门文章