现在的位置: 首页 > 综合 > 正文

最大0,1子矩阵

2013年12月09日 ⁄ 综合 ⁄ 共 673字 ⁄ 字号 评论关闭

 在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多
 
一行一行的求,如果这行的第j个是1 , 这 h[j]++; 否则 h[j] = 0;
然后对求第一行到这行的最大全1矩阵。
例如这行的h值为 5 1 1 5 3 5    这最大全1矩阵的和应该为9。
求这个需要两个数组 l[], r[] 分别表示以h[j]为矩阵的高的左边界和有边界:
for(j = 0; j < m; j ++)
        {
            l[j] = j;
            while(l[j] > 0 && h[j] <= h[l[j] - 1])
                l[j] = l[l[j] - 1];
        }
5 的左边界为   0
1 的左边界为1< 5, 1 的左边界肯定在5的左边界的左边 l[j] = l[l[j]–1]

 

 

 

 

#include <iostream>
using namespace std;

#define MAXN 2010
int h[MAXN],r[MAXN],l[MAXN];
int 
map[MAXN][MAXN];

char str[2];
int 
n,m;

void all_0_matrix()
{
    
int i,j,max 0;
    
memset(h,0,sizeof(h));

    for(i 0ni++)
    {
        
for(j mj++)
        {
            
if(map[i][j] == 0)
                h[j] ++;

            
else 
h[j] 0

抱歉!评论已关闭.