记录编号	97284	评测结果	ATTTTTTETT
题目名称	[USACO Jan14]建造滑雪场	最终得分	10
用户昵称	Miku_lyt	是否通过	未通过
代码语言	C++	运行时间	8.478 s
提交时间	2014-04-18 11:34:23	内存使用	35.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct ski{
  int f[10][10];
  int lastx,lasty;
  };

  ski q[100001];
  int n,m;
  char op;
  int l=1;
  int r=0;
  int mid;
  int g[101][101];
  int h[101][101];
  int f[101][101];

bool all(ski now){
  for (int i=1;i<=n;i++){
    for (int j=1;j<=m;j++){
      if (now.f[i][j]!=2){
        return 0;
        }
      }
    }
  return 1;
  }
  
bool check(int x,int y,ski now,int B){
  if (now.lastx==x&&now.lasty==y){
    return 0;
    }
  int flag=now.f[x][y];
  bool flag2=1;
  for (int i=x;i<x+B;i++){
    for (int j=y;j<y+B;j++){
      if (now.f[i][j]!=2){
        flag2=0;
        }
      if (now.f[i][j]!=flag&&now.f[i][j]!=2){
        return 0;
        }
      }
    }
  if (flag2){
    return 0;
    }
  return 1;
  }

bool judge(int B){
  if (B==1){
    return 1;
    }
  ski now,newq;
  int l=0;
  int r=1;
  memcpy(now.f,f,sizeof(now.f));
  now.lastx=0;
  now.lasty=0;
  q[1]=now;
  while (l!=r){
    l=(l%100000)+1;
    now=q[l];
    if (all(now)){
      return 1;
      }
    for (int i=1;i<=n-B+1;i++){
      for (int j=1;j<=m-B+1;j++){
        if (check(i,j,now,B)){
          memcpy(newq.f,now.f,sizeof(newq.f));
          newq.lastx=i;
          newq.lasty=j;
          for (int k=i;k<i+B;k++){
            for (int l=j;l<j+B;l++){
              newq.f[k][l]=2;
              }
            }
          if (all(newq)){
            return 1;
            }
          r=(r%100000)+1;
          q[r]=newq;
          }
        }
      }
    }
  return 0;
  }

int main(){
  freopen("skicourse.in","r",stdin);
  freopen("skicourse.out","w",stdout);

  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++){
    op=getchar();
    for (int j=1;j<=m;j++){
      op=getchar();
      if (op=='R'){
        f[i][j]=1;
        }
      else{
        f[i][j]=0;
        }
      }
    }
    
  for (int i=1;i<=n;i++){
    for (int j=1;j<=m;j++){
      if (f[i][j]){
        g[i][j]=min(g[i-1][j-1],min(g[i-1][j],g[i][j-1]))+1;
        h[i][j]=0;
        }
      else{
        h[i][j]=min(h[i-1][j-1],min(h[i-1][j],h[i][j-1]))+1;
        g[i][j]=0;
        }
      r=max(r,max(g[i][j],h[i][j]));
      }
    }
    
  int ans=r;
  while (!judge(ans)){
    ans--;
    }
  printf("%d\n",ans);
    
  return 0;
  }