呵呵，感谢楼上的指正，可惜这楼不是我打的地基，否则真想给你加两分
修改了笔误及逻辑上的错误，不过没有在代码级做优化，有兴趣你再拿到OJ上去测试一下。
至于计算范围，楼主给的范围只是64 X 64。需要的话改一下两个宏就可以， 这不是问题。

#include <stdio.h>

 
#define MAX_M    64
#define MAX_N    64

 
int MaxRect(char *map, int rows, int cols)

 {
     int max = 0, i, j, k, t;
     for(i = 0; i < rows; i++)
     for(j = 0; j < cols; j++)
     {
         if(map[i * cols + j]) continue;
         for(k = 1; i + k < rows && j + k < cols; k++)
         {
             for(t = 0; t <= k; t++) if(map[(i + k) * cols + j + t]) break;
             if(t <= k) break;
             for(t = 0; i < k; t++) if(map[(i + k + t) * cols + j]) break;
             if(t < k) break;
         }
         if(k > max) max = k;
     }
     return max;

 }

 
int main()

 {
     char map[MAX_M * MAX_N];
     int rows, cols, count, i;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         count = rows * cols;
         for(i = 0; i < count; scanf("%d", &map[i++]));
         printf("%d\n", MaxRect(map, rows, cols));
     }
     return 0;

 }

优化。。。


你的时间比我用的多。。。本来以为我想错啦，到网站上去OJ一下，答案是错误，他说时间超时。。。。。


上面那个网站就是那个题目的原题。。。。。。

这个题目是动态规划问题。。。。

这样虽然不是很好的DP解法。。但是真的想不到其他的，要是另一样的话那样就会发跟多的时间空间。。。。。。

你用啦三成for一般的OJ上市通不过的。。。。。。。。

本来没当回事的一道题，你的质疑再次提起了我的兴趣。
我重新分析了题目，构造出了下面的算法。你可以认为它是动态规划法，其实严格说来，它是贪心算法，因为它有很强的最优子结构。
算法很简单，你一看就明白了。其时间复杂度是O(n)。
为了保证代码的正确性，我亲自去你给的OJ提交了一次（虽然我不喜欢这个OJ）。AC。耗时367ms。
很高兴和你讨论问题

#include <stdio.h>

 
#define MAX_M    3000
#define MAX_N    3000

short int MAP[MAX_M][MAX_N];

 
int MaxRect(short int map[][MAX_N], int rows, int cols)
{
    int max = 0, min, i, j;
    for(i = 0; i < rows; i++)
    for(j = 0; j < cols; j++)
    {
        if(map[i][j] < 0) continue;
        if(i == 0 || j == 0) min = 0;
        else
        {
            min = map[i - 1][j];
            if(map[i - 1][j - 1] < min) min = map[i - 1][j - 1];
            if(map[i][j - 1] < min) min = map[i][j - 1];
            if(min < 0) min = 0;
        }
        map[i][j] = min + 1;
        if(max < map[i][j]) max = map[i][j];
    }
    return max;
}

 
int main()

 {
     int rows, cols, i, j, t;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         for(i = 0; i < rows; i++)
         for(j = 0; j < cols; j++)
         {
             scanf("%d", &t);
             MAP[i][j] = (t) ? -1 : 0;
         }
         printf("%d\n", MaxRect(MAP, rows, cols));
     }
     return 0;

 }

laoyang103早！我正在优化代码，不小心发现你也提交了这一题，而且占用内存一样，时间虽然差了一毫秒。莫非你也在测试我的代码？
已经优化完成。内存消耗由5892KB降到44KB。执行时间由367MS降到338MS。
之子于归 是我。

我在学习你的代码

#include <stdio.h>
#include <string.h>
int main()
{
    int w[3001]={0}; //保存规划到前面行规划的结果，即每一列到本行并且包括本行的最长连续0长度
    //如果本行的某一列为1 那么这个结果必为0  w[0] 保存最有子结构的结果
    int l=0,r=0,i=0,max=0,temp=0,j = 0;
    while(scanf("%d%d",&l,&r))
    {        
        if(0 == l && 0 == r)
            break;
        for(i = 1;i<=l;i++)
        {
            max = 0;
            for(j = 1;j<=r;j++)//计算到本行的每一列连续0的个数
            {
                scanf("%d",&temp);
                if(0 == temp)
                    w[j]++;
                else
                    w[j] = 0;
            }
            for(j = 1;j<=r;j++)//遍历本行结果 更新w[0]
            {
                if(w[j]>w[0])//寻找连续的并且连续0个数大于w[0]的连续列个数
                    max++;
                else
                    max = 0;
                if(max>w[0])//如果找到了比w[0]大的  那么更新w[0]
                {
                    w[0]++;
                    break;
                }
            }
        }
        printf("%d\n",w[0]);
        memset(w,0,sizeof(w));//清空结果
    }
    return 0;
}

上面代码不是我发明的  我也是根据高人的指点

其思路为：按行规划  用一个数组记录前面已经规划行

并且包含当前正在规划行的最长连续0的长度  (w[0]号元素用来保存子结构结果)

然后在当前规划行更新结果  更新条件有两个  一个是找到最长连续零（w[j]）个数大于w[0] 的列

另一个必须找到大于w[0]个这样的列  而且他们必须连续  就可以构成一个边长为w[0]+1的正方形了

我当时做这个题的时候也是用的矩形的动态规划  但是想成左上角相邻的三个取最大了  看到你矩形规划的代码学习一下

[ 本帖最后由 laoyang103 于 2011-7-29 10:43 编辑 ]

呵呵，和我优化后的差不多。算法的本质并没有改变。

#include <stdio.h>

 
#define MAX_N    3000

int main()

 {
     int rows, cols, i, j, t, max, min;
     int a[MAX_N], b[MAX_N], *pa, *pb, *pt;
     for(;;)
     {
         scanf("%d%d", &rows, &cols);
         if(rows == 0 || cols == 0) break;
         max = 0;
         for(j = 0; j < cols; j++)
         {
             scanf("%d", &t);
             a[j] = (t) ? -1 : (max = 1);
         }
         pa = a;
         pb = b;
         for(i = 1; i < rows; i++)
         {
              scanf("%d", &t);
             pb[0] = (t) ? -1 : 1;
                for(j = 1; j < cols; j++)
             {
                 scanf("%d", &t);
                 if(t) pb[j] = -1;
                 else
                 {
                     min = pb[j - 1];
                     if(pa[j - 1] < min) min = pa[j - 1];
                     if(pa[j] < min) min = pa[j];
                     if(min < 0) min = 0;
                     pb[j] = min + 1;
                     if(pb[j] > max) max = pb[j];
                 }
            }
            pt = pa;
            pa = pb;
            pb = pt;
        }
        printf("%d\n", max);
     }
     return 0;

 }

mark