[已解决]二维二进制矩阵

乐乐学编程

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

输入:

[
   ["1","0","1","0","0"],

   ["1","0","1","1","1"],

   ["1","1","1","1","1"],

   ["1","0","0","1","0"]

]

输出: 6

PS: 请用C语言回答，C++没学，看不懂代码，你回答得再好，最佳答案也不能是你的，请谅解 !

最佳答案

月排行榜 / 总排行榜

风过无痕1989

2020-10-28 01:46:19

// use option -std=c99, -std=gnu99, -std=c11 or -std=gnu11

#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 );
}

跳转到最佳答案楼层

风过无痕1989

// use option -std=c99, -std=gnu99, -std=c11 or -std=gnu11

#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 );
}

乐乐学编程

谢谢解答!