记录编号	97707	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]建造滑雪场	最终得分	100
用户昵称	ys	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2014-04-20 07:36:41	内存使用	0.37 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<list>
#include<deque>
using namespace std;
const int SIZEN=110;
int N,M;
int color[SIZEN][SIZEN]={0};
deque<pair<int,int> > Q;
bool inq[SIZEN][SIZEN]={0};
bool allgrey(void){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++) if(color[i][j]) return false;
	}
	return true;
}
int isclear(int x,int y,int K){
	int col=0;
	for(int i=x;i<x+K;i++){
		for(int j=y;j<y+K;j++){
			if(!color[i][j]) continue;
			if(!col) col=color[i][j];
			if(col!=color[i][j]) return 0;
		}
	}
	return col;
}
void stamp(int x,int y,int K,int t){//盖成t
	for(int i=x;i<x+K;i++){
		for(int j=y;j<y+K;j++){
			color[i][j]=t;
		}
	}
	inq[x][y]=true;//此块之后不必扩展
}
bool BFS(int K){
	if(Q.empty()) return false;
	while(!Q.empty()){
		int x=Q.front().first,y=Q.front().second;
		Q.pop_front();
		inq[x][y]=false;
		int nowc=isclear(x,y,K);
		if(!nowc) continue;
		stamp(x,y,K,0);
		for(int i=x-K;i<=x+K-1;i++){
			for(int j=y-K;j<=y+K-1;j++){
				if(i<1||j<1) continue;
				if(i+K-1>N||j+K-1>M) continue;
				if(inq[i][j]) continue;
				inq[i][j]=true;
				Q.push_back(make_pair(i,j));
			}
		}
	}
	return allgrey();
}
bool teststamp(int K){
	memset(inq,0,sizeof(inq));
	Q.clear();
	for(int i=1;i<=N-K+1;i++){
		for(int j=1;j<=M-K+1;j++){
			if(isclear(i,j,K)){
				Q.push_back(make_pair(i,j));
				inq[i][j]=true;
			}
		}
	}
	return BFS(K);
}
void work(void){
	for(int i=min(N,M);i>=1;i--){
		if(teststamp(i)){
			printf("%d\n",i);
			return;
		}
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	char ch;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			cin>>ch;
			if(ch=='R') color[i][j]=1;
			else color[i][j]=2;
		}
	}
}
int main(){
	freopen("skicourse.in","r",stdin);
	freopen("skicourse.out","w",stdout);
	read();
	work();
	return 0;
}