记录编号	97475	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]建造滑雪场	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2014-04-19 09:10:15	内存使用	0.48 MiB

#include<cstdio>
using namespace std;
const int MAXMN=100+10;
int M,N,f[MAXMN][MAXMN][2]={0},map[MAXMN][MAXMN][2];///
//f[i][j][0/1]表示以(i,j)为左上角顶点的正方形的最大边长，0表示全部为R，1表示全部为S
int min(int a,int b,int c=(1<<30)){if(a>b)a=b;if(a>c)a=c;return a;}
int max(int a,int b){return a>b?a:b;}
int main()
{
	freopen("skicourse.in","r",stdin);
	freopen("skicourse.out","w",stdout);
	scanf("%d%d",&M,&N);
	int i,j,sx,sy,best,ans=(1<<30),h;
	char ch;
	for(i=1;i<=M;i++)
	{
		scanf("\n");
		for(j=1;j<=N;j++)
		{
			scanf("%c",&ch);
			if(ch=='R')f[i][j][0]=map[i][j][0]=1;
			else f[i][j][1]=map[i][j][1]=1;
		}
	}
	sx=sy=1;
	best=0;
	while(true)
	{
		best=0;
		for(i=1;i<=M;i++)
		{	
			for(j=1;j<=N;j++)
			{
				if(map[i][j][0])
					f[i][j][0]=min(f[i-1][j-1][0],f[i-1][j][0],f[i][j-1][0])+1;
				if(map[i][j][1])	
					f[i][j][1]=min(f[i-1][j-1][1],f[i-1][j][1],f[i][j-1][1])+1;
				if(f[i][j][0]!=f[i][j][1])
				{
					h=max(f[i][j][0],f[i][j][1]);
					if(h>best)
					{sx=i;sy=j;best=h;}
				}
			}
		}
		if(best==0)break;
		ans=min(ans,best);
		for(i=sx-best+1;i<=sx;i++)
			for(j=sy-best+1;j<=sy;j++)
				map[i][j][0]=map[i][j][1]=true;
	}
	printf("%d",ans);
	return 0;
}