题解 P3100 【[USACO14JAN]建造滑雪场Building a Ski Course】
一道好（考智商）题。
看到求最大，我们不难想到用二分。如果你是这样想的话，那么恭喜你！
这样行不通。
我们不妨换种思路想（很难想到，对于我来说）。假设答案是k，那么读入数据（也就是最终矩阵）中必然有一个边长至少为k的全由同一种颜色组成的正方形，不然你最后一次进行标记时这个k*k的正方形应该在哪里。
然后我们把这个正方形中的所有点标记为任意颜色（即把它看做R，S通用）。为什么呢？这样做我们相当于撤销了当前的最后一次操作，而之前的操作又不确定这个位置标记的到底是哪种颜色。
当然，为了确保答案最优，这个正方形应该是最大的。
我们继续进行撤销操作（也就是逆推），然后继续求当前的最大正方形，直到没有点还有某种确定的颜色（意思是所有点都被标记了）。对于每一次求得的正方形边长取个min就是答案。
当然，最坏情况是每次找到的正方形边长都很小（甚至都为1），那么我们就要加个“可行性”剪枝了————在找了很多次正方形后带着当前得到的答案直接退出（事实证明你至少需要找不到2000一点的次数）
PS：一个点不能同时作为两个正方形的起始点（我用的是右下角）
上代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,sum,cnt,now,ans,l,r,f[101][101],g[101][101],mp[101][101],a[101][101];
char s[1010];
int main(){
scanf("%d%d",&n,&m);
ans=min(n,m);
for(i=1;i<=n;i++){
scanf("%s",s+1);
for(j=1;j<=m;j++)
if(s[j]=='R')a[i][j]=1;
else a[i][j]=2;
}
now=n*m;
while(now){
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
g[i][j]=min(g[i-1][j],min(g[i][j-1],g[i-1][j-1]))+1;
if(a[i][j]==1)g[i][j]=0;
if(a[i][j]==2)f[i][j]=0;
if(!mp[i][j]&&max(f[i][j],g[i][j])>sum){
sum=max(f[i][j],g[i][j]);
l=i;r=j;
}
}
mp[l][r]=1;
ans=min(ans,sum);
for(i=l-sum+1;i<=l;i++)
for(j=r-sum+1;j<=r;j++){
if(a[i][j])now--;
a[i][j]=0;
}
cnt++;
if(cnt>5000)break;
}
printf("%d",ans);
}