记录编号	139491	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]黑白染色	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.851 s
提交时间	2014-11-12 15:07:44	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEn=60,SIZEN=2610,INF=0x7fffffff/2;
int N;
bool black[SIZEN]={0};
int n,m;
int board[SIZEn][SIZEn]={0};
char str[SIZEn]={0};
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
vector<pair<int,int> > c[SIZEN];
int hash(int x,int y){
	return x*m+y;
}
int f[SIZEN];
queue<int> Q;
bool inq[SIZEN];
int SPFA(int S){//返回最大值
	for(int i=0;i<N;i++) f[i]=INF;
	memset(inq,0,sizeof(inq));
	while(!Q.empty()) Q.pop();
	f[S]=0;inq[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(f[x]+c[x][i].second<f[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
	int ans=-1;
	for(int i=0;i<N;i++) if(black[i]) ans=max(ans,f[i]);
	return ans;
}
void work(void){
	int ans=INF;
	for(int i=0;i<N;i++) ans=min(ans,SPFA(i)+1);
	printf("%d\n",ans);
}
void makegraph(void){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int d=0;d<4;d++){
				int i1=i+dx[d],j1=j+dy[d];
				if(i1<0||i1>n-1||j1<0||j1>m-1) continue;
				c[hash(i,j)].push_back(make_pair(hash(i1,j1),board[i][j]^board[i1][j1]));
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	N=n*m;
	for(int i=0;i<n;i++){
		scanf("%s",str);
		for(int j=0;j<m;j++){
			board[i][j]=(str[j]=='B')?1:0;
			if(board[i][j]==1) black[hash(i,j)]=true;
		}
	}
}
int main(){
	freopen("nt2012_paint.in","r",stdin);
	freopen("nt2012_paint.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}