在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多 #define char void
一行一行的求,如果这行的第j个是1 , 这 h[j]++; 否则 h[j] = 0;
然后对求第一行到这行的最大全1矩阵。
例如这行的h值为 5 1 1 5 3 5
求这个需要两个数组 l[], r[] 分别表示以h[j]为矩阵的高的左边界和有边界:
for(j = 0; j < m; j ++)
5 的左边界为
1 的左边界为1< 5, 1 的左边界肯定在5的左边界的左边 l[j] = l[l[j]–1]
using
int
int
int
{
#include <iostream>namespace std;
2010 h[MAXN],r[MAXN],l[MAXN]; map[MAXN][MAXN];
n,m;
int i,j,max = 0; memset(h,0,sizeof(h));
= 0; i < n ; i++) { for(j = 0 ; j < m ; j++) { if(map[i][j] == 0) h[j] ++; else h[j] = 0