problem_square.cpp

ACM中南大学找出最大的正方形

#include <iostream>
#include <string.h>
using namespace std;
#define LIMIT 1001

char map[LIMIT][LIMIT];
int xm[LIMIT], ym[LIMIT], sm[LIMIT],
    n, t, ans;


int main(){
  int i, j, k;

   for (i=0;i<=n;i++)
	 for (j=0;j<=n;j++)
		 map[i][j]=0;


  cin>>n>>t;
  for(k = 0; k < t; k++){
    cin>>i>>j;
    map[i][j] = 1;
  }
 

for (i=0;i<=n;i++)
  {
	  xm[i]=0;
	  ym[i]=0;
  }

  ans = 0;
  for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++)
      if(map[i][j]){
        xm[j] = 0;
        ym[j] = 0;
      }else{
        xm[j] ++;
        ym[j] = ym[j - 1] + 1;
      }
    for(j = n; j >= 1; j--){
      sm[j] = sm[j - 1] + 1;
      if(xm[j] < sm[j]) sm[j] = xm[j];
      if(ym[j] < sm[j]) sm[j] = ym[j];
      if(sm[j] > ans) ans = sm[j];
    }
  }
  cout<<ans<<endl;

  return 0;
}