Question

c++题目 输入是一个n*m的01矩阵，要求找到其中最大的全0字矩阵

input
第一行是两个整数n,m(n,m<=300)
以后n行，每行m个数，每个数都是0或者1
所有数据空格分隔
Output
只有一个整数，最大的全0矩阵的size
Sample Input

6 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0

Sample Output
10
我的程序 为什么提交时是错误的
#include<iostream>
using namespace std;
bool check(int,int,int);
int trr(int,int,int);
int a[301][301],n;
int main()
{
int m,i,j,x,k,max=0;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
cin>>a[i][j];
for(i=1;i<=n;i++)
{
j=1;
do
{
x=0;
while(a[i][j]==0&&j<=m)
{
x++;
j++;
}
if (x>0) k=trr(i,j-x,j-1);
if (k>max) max=k;
while(a[i][j]==1&&j<=m) j++;
}while(j<=m);
}
cout<<max<<endl;
return 0;
}

bool check(int xx,int yy,int zz)
{
for (int q=yy;q<=zz;q++)
{
if(a[xx][q]==1) return false;
}
return true;
}

int trr(int aa,int bb,int cc)
{
int h=1,t; bool ans;
t=aa;ans=true;
while(t>1&&ans)
{
ans=check(t-1,bb,cc);
if (ans) h++;
t--;
}
t=aa;ans=true;
while(t<n&&ans)
{
ans=check(t+1,bb,cc);
if (ans) h++;
t++;
}
return h*(cc-bb+1);
}

Answer 1

这种问题最好把自己的思路说下，不然没人能看懂你的代码。
你这样做肯定是不对的，这个题其实就是最大子矩阵，只不过把0的权设为1，1的权设为负无穷，这样求出来的肯定是最大的全是0的矩阵，仔细看一下我得做法，用的是动态规划。
顺便问下你去哪里交的题？我也去看下

#include <cstdio>

const int Max_Int = 0xfffffff;

int map[ 301 ][ 301 ], opt[ 301 ], n, m, maxn;

void init( )
{
      int i, j, t;
      scanf("%d%d", &n, &m);
      for ( i = 0; i < n; i++ )
            for ( j = 0; j < m; j++ )
            {
                  scanf("%d", &t);
                  if ( t == 0 )
                        map[ i ][ j ] = 1;
                  else
                        map[ i ][ j ] = -Max_Int;
            }
      maxn = 0;
}

void work( )
{
      int i, j, k, t;
      for ( i = 0; i < n; i++ )
            for ( j = i; j < n; j++ )
            {
                  t = 0;
                  for ( k = 0; k < m; k++ )
                  {
                        if ( j == i )
                              opt[ k ] = map[ i ][ k ];
                        else
                              opt[ k ] += map[ j ][ k ];
                        t += opt[ k ];
                        if ( t < 0 )
                              t = 0;
                        if ( maxn < t )
                              maxn = t;
                  }
            }
}

void print( )
{
      printf("%d", maxn);
}

int main( )
{
      init( );
      work( );
      print( );
      return 0;
}

Answer 2

using namespace std;
bool check(int,int,int);
int trr(int,int,int);
int a[301][301],n;
int main()
{
int m,i,j,x,k,max=0;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
cin>>a[i][j];
for(i=1;i<=n;i++)
{
j=1;
do
{
x=0;
while(a[i][j]==0&&j<=m)
{
x++;
j++;
}
if (x>0) k=trr(i,j-x,j-1);
if (k>max) max=k;
while(a[i][j]==1&&j<=m) j++;
}while(j<=m);
}
cout<<max<<endl;
return 0;
}

bool check(int xx,int yy,int zz)
{
for (int q=yy;q<=zz;q++)
{
if(a[xx][q]==1) return false;
}
return true;
}

int trr(int aa,int bb,int cc)
{
int h=1,t; bool ans;
t=aa;ans=true;
while(t>1&&ans)
{
ans=check(t-1,bb,cc);
if (ans) h++;
t--;
}
t=aa;ans=true;
while(t<n&&ans)
{
ans=check(t+1,bb,cc);
if (ans) h++;
t++;
}
return h*(cc-bb+1);
}给你个测试数据：

4 3
0 0 0
0 0 0
1 1 1
1 1 1
就有错误了~！#include <cstdio>

const int Max_Int = 0xfffffff;

int map[ 301 ][ 301 ], opt[ 301 ], n, m, maxn;

void init( )
{
int i, j, t;
scanf("%d%d", &n, &m);
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
{
scanf("%d", &t);
if ( t == 0 )
map[ i ][ j ] = 1;
else
map[ i ][ j ] = -Max_Int;
}
maxn = 0;
}

void work( )
{
int i, j, k, t;
for ( i = 0; i < n; i++ )
for ( j = i; j < n; j++ )
{
t = 0;
for ( k = 0; k < m; k++ )
{
if ( j == i )
opt[ k ] = map[ i ][ k ];
else
opt[ k ] += map[ j ][ k ];
t += opt[ k ];
if ( t < 0 )
t = 0;
if ( maxn < t )
maxn = t;
}
}
}

void print( )
{
printf("%d", maxn);
}

int main( )
{
init( );
work( );
print( );
return 0;

Answer 3

你代码贴全了吗？
为什么下面的函数在里主函数里都没有调用？
用你现在的程序虽然能过例子但是
给你个测试数据：

4 3
0 0 0
0 0 0
1 1 1
1 1 1
就有错误了~！

Answer 4

对每个0元素定义其极大扩展矩阵为按以下方法构造的矩阵：先向上扩展，直到遇到1或边界，然后以刚刚得到的边为基准向左右扩展，直到遇到1而不能扩展。
比如
1 0
0 0
中右下角的0的极大扩展矩阵为最右边的一列，比如
1 0 0 0
0 0 0 1
0 0 0 0
中第二行左数第二列的0的极大扩展矩阵为第一、二行中间的4个0。

可以证明最大的全0矩阵必为某个0元素的极大扩展矩阵：最大的全0矩阵（设为A）最上边必定有一些1或边界而导致这个矩阵不能再向上扩展，那么在有1或边界的列上，A中最下面一行的元素的极大扩展矩阵即为A。
比如
1 0
0 0
中右下角的0的极大扩展矩阵即为一个最大全0矩阵，比如
1 0 0 0
0 0 0 1
0 0 0 0
中第三行中间两个0的极大扩展矩阵均为最大全0矩阵。

因此我们可以通过遍历每个0元素的极大扩展矩阵来求得最大全0矩阵。对每个元素保存l,r,h三个值，分别表示从该元素到其极大扩展矩阵最左边一列的的距离、从该元素到其极大扩展矩阵最右边一列的的距离、极大扩展矩阵的高度，可以通过递推求得：
如果[i,j]（表示从上往下数第i行、从左往右数第j列的元素，下同）=0，那么
l[i+1,j]=min{l[i,j],从[i,j]到左边第一个1的距离}，
r[i+1,j]=min{r[i,j],从[i,j]到右边第一个1的距离}，
h[i+1,j]=h[i,j]+1，
否则
l[i+1,j]=从[i,j]到左边第一个1的距离，
r[i+1,j]=从[i,j]到右边第一个1的距离，
h[i+1,j]=1。
最后只需要找出所有元素中(l+r+1)h最大的即可。它的极大扩展矩阵即为最大全0矩阵。