codeforces 37 E. Trial for Chief【spfa】

想象成一层一层的染，所以相邻的两个格子连边，边权同色为0异色为1，然后答案就是某个格子到距离它最远得黑格子的最短距离的最小值

注意特判掉不需要染色的情况

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=55,inf=1e9;

int n,m,id[N][N],tot,h[N*N],cnt,ans=inf,dis[N*N];

char c[N][N];

bool v[N*N];

struct qwe

{

	int ne,to,va;

}e[N*N*5];

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

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void ins(int u,int v,int w)

{//cerr<<u<<" "<<v<<" "<<w<<endl;

	add(u,v,w);

	add(v,u,w);

}

int spfa(int s)

{

	for(int i=1;i<=tot;i++)

		dis[i]=inf;

	queue<int>q;

	v[s]=1,dis[s]=0,q.push(s);

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		v[u]=0;

		for(int i=h[u];i;i=e[i].ne)

			if(dis[e[i].to]>dis[u]+e[i].va)

			{

				dis[e[i].to]=dis[u]+e[i].va;

				if(!v[e[i].to])

				{

					v[e[i].to]=1;

					q.push(e[i].to);

				}

			}

	}

	int re=0;

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

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

			if(c[i][j]=='B')

				re=max(re,dis[id[i][j]]);

	return re+1;

}

int main()

{

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

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

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

			id[i][j]=++tot;

	bool fl=0;

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

	{

		scanf("%s",c[i]+1);

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

		{

			if(c[i][j]=='B')

				fl=1;

			if(i!=1)

				ins(id[i-1][j],id[i][j],c[i-1][j]!=c[i][j]);

			if(j!=1)

				ins(id[i][j-1],id[i][j],c[i][j-1]!=c[i][j]);

		}

	}

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

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

			ans=min(ans,spfa(id[i][j]));

	printf("%d\n",!fl?0:ans);

	return 0;

}

巴特西

codeforces 37 E. Trial for Chief【spfa】

最新文章

热门文章