#include<cstdio>
bool ok;
int f[1001][1001],m,n,ans=0;
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&ok);
if(ok)
{
f[i][j]=std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1;
ans=std::max(ans,f[i][j]);
}
}
printf("%d\n",ans);
}

超级简单代码发一份：
c++
#include<stdio.h>
#define rep(i,n) for(int i=0;i<n;++i)
int s[1001][1001],n,m,ans=1;
inline void max(int& a,int b){if(a<b)a=b;}
inline int min(int a,int b,int c){if(a>b)a=b;if(a>c)a=c;return a;}
int main(){
scanf("%d%d",&n,&m);
rep(i,n) rep(j,m) scanf("%d",s[i]+j);
rep(i,n) rep(j,m)
if(i&&j&&s[i][j])
max(ans,s[i][j]=min(s[i-1][j-1],s[i-1][j],s[i][j-1])+1);
printf("%d\n",ans);
}


var n,m,i,j,t,k,x,y:longint;
a:array[1..1000,1..1000]of longint;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
t:=1;
for i:=1 to n do
for j:=1 to m do
if a[i,j]<>0 then
begin
k:=0;
while k=0 do
begin
for x:=i to i+t do
for y:=j to j+t do
if a[x,y]=0 then
k:=1;
if k=0 then inc(t);
end;
end;
write(t);
end.

#include<cstdio>
#define INF 2000000
int a[1005][1005];
int n,m,i,j,max=1;
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++){scanf("%d",&a[i][j]);}
int min;
for(i=1;i<n;i++)
for(j=1;j<m;j++)
{if(a[i][j]==0)continue;
min=INF;
if(a[i-1][j-1]<min)min=a[i-1][j-1];
if(a[i-1][j]<min)min=a[i-1][j];
if(a[i][j-1]<min)min=a[i][j-1];
a[i][j]=min+1;
if(a[i][j]>max)max=a[i][j];
}
printf("%d",max);
return 0;
}

#include<cstdio>
#define INF 2000000
int a[1005][1005];
int n,m,i,j,max=1;
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++){scanf("%d",&a[i][j]);}
int min;
for(i=1;i<n;i++)
for(j=1;j<m;j++)
{if(a[i][j]==0)continue;
min=INF;
if(a[i-1][j-1]<min)min=a[i-1][j-1];
if(a[i-1][j]<min)min=a[i-1][j];
if(a[i][j-1]<min)min=a[i][j-1];
a[i][j]=min+1;
if(a[i][j]>max)max=a[i][j];
}
printf("%d",max);
return 0;
}

i,j,sum,n,m:longint;

楼下没用动规，比楼楼下少打几行字
var
i,j,sum:longint;
a,f:array[0..1000,0..1000]of longint;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
sum:=1;
for i:=1 to n do
for j:=1 to m do
begin
if a[i,j]=1 then f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;
if f[i,j]>sum then sum:=f[i,j];
end;
writeln(sum);
end.

var
s:array[0..1001,0..1001]of integer;
i,j,k,a,b,c,m,n,l:longint;
f:boolean;
begin
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do
read(s[i,j]);
readln;
end;
for i:=1 to m do
for j:=1 to n do
begin
if s[i,j]=1
then begin
k:=0; f:=false;
repeat
k:=k+1;
for a:=0 to k do
for b:=0 to k do
if s[i+a,j+b]=0
then f:=true;
until f;
end;
if k>c
then c:=k;
end;
writeln(c);
end.
以这题的数据范围来说，就算是模拟都能水过。。。。。。。。。。

VAR
n,m:longint;
a:array[1..1000,1..1000] of integer;
i,j,k:longint;
f:array[0..1001,0..1001] of longint;

FUNCTION min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;

BEGIN

//assign(input,'1.in');reset(input);
//assign(output,'1.out');rewrite(output);

readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(a[i,j]);
end;
readln;
end;
i:=0;j:=0;k:=0;

for i:=1 to n do
for j:=1 to m do
begin
if a[i,j]=1 then
begin
f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;
end;
end;

writeln(f[n,m]);
//close(input);close(output);
END.

比楼下的动规快一点，占内存少一点。

var f,a:array[0..1050,0..1050] of longint;
i,j,l,n,m,k:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
k:=0;
for i:=1 to n do
for j:=1 to m do
if a[i,j]=1 then
begin
f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;
if f[i,j]>k then k:=f[i,j];
end;
writeln(k);
end.
看到题目上的十分钟做完的时候我以为能一眼看出，然后我错了，当我想了7分钟的时候，我觉得肯定是题面在嘲讽人，但等我8分钟想到了后，一切都简单了，2分钟打完了。
其实思路还是很清晰的，f[i,j]表示点（i，j）为正方形右下角的点时的最小边长，因为知道正方形的话，这一点的状态只由点（i-1，j-1）（i-1，j）（i，j-1）决定，然后。。没有然后了。

神奇的方法，预处理
水水水

#include<iostream>
using namespace std;
int n,m,i,j,k,mx=0,s[1001][1001]={0};
bool map[1001][1001];
int main(){
cin>>n>>m;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)cin>>map[i][j];
for(i=1;i<=n;++i)
for(j=m;j>=1;--j)
if(map[i][j])s[i][j]=s[i][j+1]+1;
else s[i][j]=0;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
int mn=1000;
for(k=i;k<=n&&map[k][j];++k){
mn=min(mn,s[k][j]);
if(mn<k-i+1)break;
}
mx=max(mx,k-i);
}
cout<<mx;
}

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <cstdlib>
#include <math.h>
using namespace std;
int f[1001][1001];
int main(){
int i,j,k,n,m,ans=-1;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
cin>>f[i][j];
f[i][j]*=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))+1;
if(f[i][j]>=ans) ans=f[i][j];
}

cout<<ans<<endl;
system("pause");
return 0;
}

WA两次终于AC了，调试了好久
设d(i,j)为以(i,j)为右下角的最大的正方形,li(i,j)为(i,j)正上方最长连续可建筑块
lj(i,j)为(i,j)正左方最大连续可建筑块(包括自己)
初始化d(i,j)=a[i][j],a[i][j]为输入数据
如果d(i-1,j-1)>min{ lj(i,j),li(i,j) } 则d(i,j)=d(i-1,j-1)+1;
否则d(i,j)=min{ lj(i,j),li(i,j) }
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=1000+5;
int d[maxn][maxn],n,m,li[maxn][maxn],lj[maxn][maxn];
bool a[maxn][maxn];

int dp(int i,int j) {
int &ans=d[i][j];
if (!a[i][j]) return ans=0;
if (i==1||j==1) return ans=1;
int &v=d[i-1][j-1],u=min(li[i][j],lj[i][j]);;
if (u>v) ans=v+1;
else ans=u;
return ans;
}

int main() {
ios::sync_with_stdio(0);
cin>>n>>m;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) {
cin>>a[i][j];
d[i][j]=li[i][j]=lj[i][j]=(a[i][j]?1:0);
if (i>1&&a[i-1][j]) li[i][j]=li[i-1][j]+1;
if (j>1&&a[i][j-1]) lj[i][j]=lj[i][j-1]+1;
dp(i,j);
}
int ans=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (ans<d[i][j]) ans=d[i][j];
cout<<ans;
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 6928 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 6928 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 6928 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 6924 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 6928 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 6928 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 6928 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 6924 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 6928 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 6924 KiB, score = 10
Accepted, time = 45 ms, mem = 6928 KiB, score = 100

代码
#include <iostream>
#include <stdio.h>
using namespace std;
int map[1300][1300];

int height[3000];
int le[3000];
int ri[3000];
int main()
{
int n,m;
int maxans=0;

scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=m;i++)
{
le[i]=0;
ri[i]=m+1;
}
for(int i=1;i<=n;i++)
{
int l=0,r=m+1;
for(int j=1;j<=m;j++)
{ height[j]++;
if(map[i][j]==0)
{
l=j;
height[j]=0;
le[j]=0;
}
else
{
le[j]=max(l,le[j]);

}
}
for(int k=m;k>0;k--)
{
if(map[i][k]==0)
{
r=k;
height[k]=0;
ri[k]=m+1;
}
else
{
ri[k]=min(r,ri[k]);
}

}
for(int s=1;s<=m;s++)
{
if(map[i][s])
maxans=max(maxans,min(ri[s]-le[s]-1,height[s]));
}

}
printf("%d",maxans);
}

P1057盖房子
Accepted

记录信息

评测状态 Accepted
题目 P1057 盖房子
递交时间 2015-07-12 23:53:40
代码语言 C++
评测机 VijosEx
消耗时间 75 ms
消耗内存 15996 KiB
评测时间 2015-07-12 23:53:43

评测结果

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 15992 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 15996 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 15988 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 15988 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 15996 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 15988 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 15988 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 15992 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 15988 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 15996 KiB, score = 10

Accepted, time = 75 ms, mem = 15996 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n , m;
int i , j;
int a[1000 + 2][1000 + 2];
int prex[1000 + 2][1000 + 2];
int prey[1000 + 2][1000 + 2];
int f[1000 + 2][1000 + 2];
int ans;

int max( int a , int b )
{
if( a > b )
return a;
return b;
}

int mind( int a , int b , int c )
{
return min( min( a , b ) , c );
}

int dp( int x , int y )
{
if( x <= 0 || y <= 0 )
return 0;
if( x == 1 && y == 1 )
return a[x][y];
if( f[x][y] != -1 )
return f[x][y];
if( !a[x][y] )
{
f[x][y] = 0;
return f[x][y];
}
f[x][y] = mind( dp( x - 1 , y - 1 ) , prex[x][y] - 1 , prey[x][y] - 1 ) + 1;
return f[x][y];
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= m ; j++ )
scanf( "%d" , &a[i][j] );
for( j = 1 ; j <= m ; j++ )
for( i = 1 ; i <= n ; i++ )
if( a[i][j] )
prey[i][j] = prey[i - 1][j] + 1;
else
prey[i][j] = 0;
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= m ; j++ )
if( a[i][j] )
prex[i][j] = prex[i][j - 1] + 1;
else
prex[i][j] = 0;
memset( f , -1 , sizeof( f ) );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= m ; j++ )
ans = max( ans , dp( i , j ) );
cout << ans << endl;
return 0;
}

http://blog.csdn.net/slow_yangyang/article/details/46495857
欢迎来看我的思路

作为一道水题，我居然6次才AC……考虑问题还是不够全面，还有各种细节问题。
我思路如下：
预处理出每个格子(x,y)右边连续的空白位置rc[x][y]，下面的的空白位置dc[x][y]
然后d[x][y]表示以(x,y)为左上角的最大正方形边长
如果(x,y)不能建筑或者超出边界则为0，
否则有：d[x][y]=min{d[x+1][y+1],rc[x][y],dc[x][y]}+1
记忆化搜索（dp也行）

Block code

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;

int map[maxn][maxn];
int d[maxn][maxn];
int rc[maxn][maxn]; //右边最近的石头的距离
int dc[maxn][maxn]; //下面最近石头距离
int ans=0;
int n,m;

int getd(int x,int y)
{
if(x>=n||y>=m)
return 0;
if(d[x][y]!=-1)
return d[x][y];
return d[x][y]=(map[x][y]==1?min(dc[x][y],min(getd(x+1,y+1),rc[x][y]))+1:0);
}

int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>map[i][j];

for(int i=0;i<n;i++)
for(int j=m-1;j>=0;j--)
{
if(!map[i][j])
rc[i][j]=-1;
else
rc[i][j]=rc[i][j+1]+1;
}

for(int i=0;i<m;i++)
for(int j=n-1;j>=0;j--)
{
if(!map[j][i])
dc[j][i]=-1;
else
dc[j][i]=dc[j+1][i]+1;
}

memset(d,-1,sizeof(d));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
ans=max(getd(i,j),ans);
}
cout<<ans<<endl;

return 0;
}

这题可以用单调队列（其实已经退化成栈了）来实现
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[1001][1001];
int N,M;
struct node
{
int v;
int t;
}line[10001];
int main()
{
while(cin>>N>>M)
{
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==1)
{
a[i][j]+=a[i-1][j];
}
}
}
int rear,ans=0,temp;
for(int i=1;i<=N;i++)
{
rear=0;
for(int j=1;j<=M;j++)
{
temp=j;
while(rear>=1 && a[i][j]<line[rear].v)
{
ans=max(ans,min(j-line[rear].t,line[rear].v));
temp=line[rear].t;
rear--;
}
line[++rear].v=a[i][j];
line[rear].t=temp;
}
while(rear>=1)
{
ans=max(ans,min(M-line[rear].t+1,line[rear].v));
rear--;
}
}
cout<<ans<<endl;
}
}

var
i,j,k,n,m,s,t,ans,x,y:longint;
d,a:array[0..1000,0..1000]of longint;
function min(i,j,k:longint):longint;
begin
if i>j then i:=j;
if i>k then i:=k;
exit(i);
end;
function max(i,j:longint):longint;
begin
if i>j then exit(i);
exit(j);
end;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do read(a[i,j]);readln;
end;
for i:=1 to n do
if a[i,1]=0 then d[i,1]:=0 else d[i,1]:=1;
for j:=1 to n do
if a[1,j]=0 then d[1,j]:=0 else d[1,j]:=1;
for i:=2 to n do
for j:=2 to n do
begin
if a[i,j]=0 then d[i,j]:=0
else d[i,j]:=min(d[i-1,j-1],d[i-1,j],d[i,j-1])+1;
end;
for i:=1 to n do
for j:=1 to n do
ans:=max(ans,d[i,j]);
writeln(ans);
end.
原题：usaco 巨大的牛棚

动态规划，走了一点弯路，不过原理是相同的，这样写可读性更好。
a[i,j]表示以i,j为左上角的最大正方形，它的来源有两个：下面和左面，取两者中的最小值x。
若a[i+x][j+x]位置处也是1，表明可以扩大a[i,j]=x+1;
否则a[i,j]=x;
#include<iostream>
#include<string.h>
using namespace std;
int a[1003][1003];
int main(){
freopen("in.txt", "r", stdin);
int w, h;
cin >> w >> h;
int i, j;
memset(a, 0, sizeof(a));
for (i = 0; i < w; i++)
for (j = 0; j < h; j++)cin >> a[i][j];
int mm = 0;
for (i = w - 1; i >= 0; i--){
for (j = h - 1; j >= 0; j--){
if (a[i][j] == 1){
int x = a[i][j + 1];
if (a[i + 1][j] < x){
x = a[i + 1][j];
}
if (a[i + x][j + x] !=0)
a[i][j] = x + 1;
else a[i][j] = x;

if (a[i][j]>mm)mm = a[i][j];
}
}
}
cout << mm << endl;
return 0;
}