http://acm.timus.ru/problem.aspx?space=1&num=1221
算是枚举的 题目意思是必须划出这样的 11011
10001
00000
10001
11011
注意中间必须是完整的0，不多不少，旁边的1也是如此 不多不少 才可以
题目很简单 预处理出1的个数 以及以当前0为最低顶角的最大正方形的边长 判断一下1的个数是否满足就可
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
using namespace std;
int a[][],dp[][],sum[][];
int main()
{
int i,j,n,maxz,g;
while(cin>>n)
{
if(!n) break;
memset(sum,,sizeof(sum));
memset(dp,,sizeof(dp));
maxz=;
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
{
cin>>a[i][j];
if(a[i][j]==) dp[i][j] = ;
sum[i][j] = sum[i-][j]+sum[i][j-]-sum[i-][j-];
if(a[i][j]==) sum[i][j]++;
}
for(i = ; i <= n ; i++)
for(j = ; j <= n ;j++)
if(a[i][j]==)
{
int k = (min(dp[i-][j],dp[i-][j-]),dp[i-][j+]);
if(i>=*k+&&a[i-*k][j]==)
dp[i][j] = k+;
else
dp[i][j] = ;
//cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
}
int b[] = {};
b[] = ;
for(i = ; i <= ; i++)
b[i] = b[i-]+*(i-);
for(i =; i <= n ; i++)
for(j = ; j <= n ;j++)
{
if(a[i][j]==)
{
int x=;
for(g = j ; g >= ; g--)
if(a[i][g]==)
break;
else x++;
if(i<*x+||j<*x+) continue;
int s = sum[i][j]-sum[i-*x-][j]-sum[i][j-*x-]+sum[i-*x-][j-*x-];
//if(i==5&&j==5)
//cout<<dp[i][j-x]<<" "<<x<<" "<<sum[i][j]<<endl;
if(dp[i][j-x]==x+&&s==(*x+)*(*x+)-b[x+])
maxz = max(maxz,*x+);
}
}
if(maxz)
cout<<maxz<<endl;
else
puts("No solution");
} return ;
}