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;
}