找出最大矩阵,并返回其面积
给定一个仅包含 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 ); }