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

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<deque>
using namespace std;
ifstream fi("skicourse.in");
ofstream fo("skicourse.out");
int M,N;
int color[110][110];
deque <pair<int,int> > Q;
bool inq[110][110];
bool BFS(int k)
{
	bool done=true;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
			if(color[i][j]>0)done=false;
	if(done)return true;//完成涂灰
	if(Q.empty())return false;
	int len=Q.size();
	pair<int,int> u;
	while(len--)
	{
		u=Q.front();
		Q.pop_front();
		inq[u.first][u.second]=false;
		int co=0;
		for(int p=u.first;p<u.first+k;p++)
			for(int q=u.second;q<u.second+k;q++)
				if(!co)
					co=color[p][q];
				else
					if(color[p][q]!=co && color[p][q]!=0)
						goto WRONG;
		for(int p=u.first;p<u.first+k;p++)
			for(int q=u.second;q<u.second+k;q++)
				color[p][q]=0;
		inq[u.first][u.second]=true;//涂灰那以后再也不用拓展啦
		for(int p=u.first-k;p<=u.first+k-1;p++)
			for(int q=u.second-k;q<=u.second+k-1;q++)
			{
				if(p<1 || q<1)continue;
				if(p+k-1>M || q+k-1>N)continue;
				if(inq[p][q])continue;
				inq[p][q]=true;
				Q.push_back(make_pair(p,q));
			}
		WRONG:;
	}
	return BFS(k);
}
int main()
{
	fi>>M>>N;
	char ch;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
		{
			fi>>ch;
			if(ch=='R')
				color[i][j]=1;
			else
				color[i][j]=2;
		}
	int co=0;
	for(int k=min(M,N);k>=1;k--)//从大到小枚举答案
	{
		memset(inq,0,sizeof(inq));//点亮队列
		Q.clear();
		for(int i=1;i<=M-k+1;i++)
		{
			for(int j=1;j<=N-k+1;j++)
			{
				co=0;
				for(int p=0;p<k;p++)
					for(int q=0;q<k;q++)
						if(!co)
							co=color[i+p][j+q];
						else
							if(color[i+p][j+q]!=co && color[i+p][j+q]!=0)
								goto NEXT;//不是最后一块正方形
				for(int p=0;p<k;p++)
					for(int q=0;q<k;q++)
						color[i+p][j+q]=0;
				inq[i][j]=true;
				for(int p=i-k;p<=i+k-1;p++)
					for(int q=j-k;q<=j+k-1;q++)
					{
						if(p<1 || q<1 || p>M || q>N)continue;
						if(p+k-1>M || q+k-1>N)continue;
						if(inq[p][q])continue;
						inq[p][q]=true;
						Q.push_back(make_pair(p,q));
					}
				NEXT:;
			}
		}
		if(Q.empty())continue;
		if(BFS(k)){fo<<k<<endl;return 0;}
	}
	return 0;
}