记录编号	143599	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]黑白染色	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.220 s
提交时间	2014-12-16 12:59:25	内存使用	0.66 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define h(x,y) (m*(x-1)+y)
#define Maxn 110
using namespace std;
int n,m,dis[Maxn*Maxn];
vector<int> G[Maxn*Maxn],C[Maxn*Maxn];
queue<int> q;
int ans=0x3fffffff;
bool flag[Maxn*Maxn]={0};
char ch[Maxn][Maxn];
void spfa(int s){
	memset(flag,0,sizeof(flag));
	memset(dis,0x3f,sizeof(dis));
	q.push(s); dis[s]=0; flag[s]=true;
	while(!q.empty()){
		int now=q.front(); q.pop();
		flag[now]=false;
		for(int i=0;i<G[now].size();i++){
			if(dis[G[now][i]]>dis[now]+C[now][i]){
				dis[G[now][i]]=dis[now]+C[now][i];
				if(!flag[G[now][i]]){
					flag[G[now][i]]=true;
					q.push(G[now][i]);
				}
			}
		}
	}
	int tmp=-0x3fffffff;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ch[i][j]=='B'&&dis[h(i,j)]>tmp) tmp=dis[h(i,j)];
		}
	}
	ans=min(ans,tmp+1);
}
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
bool pass(int x,int y){
	return x<=n&&x>=1&&y<=m&&y>=1;
}
int main(){
	freopen("nt2012_paint.in","r",stdin);
	freopen("nt2012_paint.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<4;k++){
				if(pass(i+xx[k],j+yy[k])){
					G[h(i,j)].push_back(h(i+xx[k],j+yy[k]));
					C[h(i,j)].push_back(ch[i][j]==ch[i+xx[k]][j+yy[k]]?0:1);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) spfa(h(i,j));
	}
	printf("%d\n",ans);
	return 0;
}