c语言：输入是一个n*m的矩阵，要求找到其中最大的全0字矩阵。怎么算？

Question

全零子矩阵
看不太懂啊。我觉着楼下两位算法好像有问题啊。
能不能详细解释下？

Answer 1

这个题其实就是最大子矩阵，只不过把0的权设为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

这个题其实就是最大子矩阵，只不过把0的权设为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 3

说一下算法：
－－－－－－－－－－－－－－－－－－－－－
[i,j]从[0,0]-->[n][m]循环
{{//循环开始
if([i][j]==0)
{
//纵向判断
k=0
while([i+k][j]==0)k++;
a=k;
//横向判断
k=0;
while([i][j+k]==0)k++;
b=k;
//保存找到的子矩阵
save(i,j,a,b);//[i,j]开始，a行b列子矩阵，可以保存到一个结构数组，或者链表
}//if结束
}}//循环结束

从保存的结构数组(或者链表)中挑出最大的一个输出
--------------------------------------------
关于最大：用元素多少比较
比如：2行3列的矩阵 比 1行7列矩阵小