当前位置:编程学习 > C/C++ >>

最大全1子矩阵

题目描述:
给出1个M*N的矩阵M1,里面的元素只有0或1,找出M1的一个子矩阵M2,M2中的元素只有1,并且M2的面积是最大的。输出M2的面积。
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 100)
第2 - N + 1行:每行m个数,中间用空格分隔,均为0或1。
Output
输出最大全是1的子矩阵的面积。
Input 示例
 
3 3
1 1 0
1 1 1
0 1 1
Output 示例
4
题目分析:
这个题目N=100时可以根据最小子矩阵和求O(N^3),但是当N范围为1000时,就要求降一个数量级了。
这里我们可以一行一行的求。
比如第一行 1 1 0 1 1 1 0 1
那么我们求和b[]={1,1,0,1,1,1,0,1}
比如第二行为1 1 0 0 0 0 1 1
那么我们继续求和b[]={2,2,0,0,0,0,0,2}......
也就是说:
if(map[i][k])
     b[k] ++;
else
     b[k] = 0;
 
这样得到了了一个直方图,不知道大家有没有求过最大直方图面积的问题
就是不同高度的直方图,求这个直方图最大的矩形面积,如何去求?
比如直方图高度为 1 2 3 2,那么最大面积是?
当以第一个为基准的时候高度为1,后面的大于都可以组成矩形,所以面积为4.当以第二个为基准,那么只有后三个可以,面积为6.同理。。。。最大面积为6.
这里也是一样,当求得了第一行到当前行的高度后,可以求出目前的最大面积。
 
我们设立两个数组l[],r[]分别表示以b[j]为基准时候的左右边界,那么一b[j]为基准的面积就变成了b[j]*(r[j]-l[j]+1),然后枚举出最大的即可。
对于l[],r[],我们可以通过下面计算方法获得:
[cpp] 
for (int j = 1; j <= N; ++ j)  
            {  
                l[j] = j;  
                while (l[j] - 1 >= 1 && b[j] <= b[l[j] - 1])  
                {  
                    l[j] = l[l[j] - 1];  
                }  
            }  
            for (int j = N; j >= 1; -- j)  
            {  
                r[j] = j;  
                while (b[j] <= b[r[j] + 1] && r[j] + 1 <= N)  
                {  
                    r[j] = r[r[j] + 1];  
                }  
            }  
 
最后可以求最大值:
[cpp] 
for (int j = 1; j <= N; ++ j)  
            {  
                if (b[j] && (b[j]*(r[j] - l[j]+1) > Max))  
                {  
                    Max = b[j]*(r[j] - l[j]+1);  
                }  
            }  
 
代码:
[cpp] 
#include <iostream>  
#include <cstdlib>  
#include <cstring>  
using namespace std;  
  
const int MAXN = 510;  
int map[MAXN][MAXN];  
int b[MAXN],l[MAXN],r[MAXN];  
  
int M,N;  
  
int main()  
{  
    while (cin >> M >> N)  
    {  
        int Max = 0;  
        memset(map,0,sizeof(map));  
        for (int i = 1; i <= M; ++ i)  
        {  
            for (int j = 1; j <= N; ++j)  
            {  
                cin >> map[i][j];  
            }  
        }  
  
        for (int j = 0; j <= N+1; ++ j)  
        {  
            b[j] = 0;  
        }  
        for (int i = 1; i <= M; ++ i)  
        {  
            for (int k = 1; k <= N; ++ k)  
            {  
                if(map[i][k])  
                    b[k] ++;  
                else  
                    b[k] = 0;  
            }  
              
            /*for (int j = 1; j <= N; ++ j) 
            { 
                int p = j; 
                while (p>=1 && b[j] <= b[p--]); 
                int q = j; 
                while(q<=N && b[j] <= b[q ++]); 
                if (b[j] && (b[j]*(q-p-1) > Max)) 
                { 
                    Max = b[j]*(q-p); 
                } 
            }*/  
            for (int j = 1; j <= N; ++ j)  
            {  
                l[j] = j;  
                while (l[j] - 1 >= 1 && b[j] <= b[l[j] - 1])  
                {  
                    l[j] = l[l[j] - 1];  
                }  
            }  
            for (int j = N; j >= 1; -- j)  
            {  
                r[j] = j;  
                while (b[j] <= b[r[j] + 1] && r[j] + 1 <= N)  
     
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,