找出最大矩阵,并返回其面积
给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
程序请用C语言,不要C++,谢谢!
程序代码:#include <stdio.h>
#include <stdint.h>
int main( void )
{
size_t map[][5] = { {1, 0, 1, 0, 0}
, {1, 0, 1, 1, 1}
, {1, 1, 1, 1, 1}
, {1, 0, 0, 1, 0} };
///////////////////////////////////////////////
const size_t row = sizeof(map)/sizeof(*map);
const size_t col = sizeof(*map)/sizeof(**map);
for( size_t c=0; c!=col; ++c )
{
size_t deepth = 0;
for( size_t r=0; r!=row; ++r )
{
if( map[r][c] != 0 )
map[r][c] = ++deepth;
else
deepth = 0;
}
}
size_t s_max = 0;
for( size_t r=0; r!=row; ++r )
{
for( size_t c=0; c!=col; ++c )
{
size_t deepth = SIZE_MAX;
for( size_t width=0; c+width!=col && map[r][c+width]!=0; ++width )
{
deepth = deepth<map[r][c+width] ? deepth : map[r][c+width];
s_max = s_max>(width+1)*deepth ? s_max : (width+1)*deepth;
}
}
}
printf( "%zu\n", s_max );
}