CF37E Trial for Chief 题解

CF37E Trial for Chief

题意：

给定一张 $N\times M$ 的网格，初始全为白色，每次可以把一个相同颜色的四连通区域染成白色或黑色，求最少的染色次数得到给定的图案。$N,M\le 50$

思路：

“你玩过画图吗？就是那种上课无聊的时候点点点然后整个图都是一个颜色了。”
就像这句话一样！我们想到可以固定一个点一直点，这样一定是最小的（手动模拟一下即可）。发现数据范围很小，所以固定的这个点可以枚举，那如何求最小值呢，向不相同的颜色连边权为 $1$ 的边，相同颜色连边权为 $0$ 的边。跑最短路，走到每个点的最短路的最大值就是这个点所需的费用。找到最小费用便是答案了。

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int N=52;
const int M=10005;
int n,m;
string s;
int mp[N][N];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
struct node{int w,nxt,v;
}e[M<<1];
int h[M],tot;
int ans;
int vis[M],dis[M];
void spfa(int s){for(int i=0;i<=tot+5;i++){dis[i]=INF;vis[i]=0;}queue<int> q;q.push(s);dis[s]=vis[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=h[u];~i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=1;q.push(v);}}}vis[u]=0;}int anss=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!mp[i][j]) anss=max(anss,dis[(i-1)*m+j]);}}ans=min(ans,anss);
}
void add(int x,int y,int w){e[++tot].nxt=h[x];e[tot].v=y;e[tot].w=w;h[x]=tot;
}
int main(){ans=INF;memset(h,-1,sizeof h);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){cin>>s;for(int j=0;j<m;j++){mp[i][j+1]=((s[j]=='W')?1:0);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x<1||y<1||x>n||y>m) continue;add((i-1)*m+j,(x-1)*m+y,(mp[x][y]!=mp[i][j]));}}}for(int i=1;i<=n*m;i++){spfa(i);}printf("%d\n",ans);return 0;
}