题目1497:面积最大的全1子矩阵

论坛 期权论坛 编程之家     
选择匿名的用户   2021-6-2 20:59   3118   0
题目描述:

在一个M * N的矩阵中,所有的元素只有0和1,从这个矩阵中找出一个面积最大的全1子矩阵,所谓最大是指元素1的个数最多。

输入:

输入可能包含多个测试样例。
对于每个测试案例,输入的第一行是两个整数m、n(1<=m、n<=1000):代表将要输入的矩阵的大小。
矩阵共有m行,每行有n个整数,分别是0或1,相邻两数之间严格用一个空格隔开。

输出:

对应每个测试案例,输出矩阵中面积最大的全1子矩阵的元素个数。

样例输入:
2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
样例输出:
0
4
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int mat[1010][1010];
int h[1010];
int l[1010];
int r[1010];
int main() 
{
 int n,m;
 while (scanf ("%d%d",&m,&n) == 2) {
  for (int i = 1;i <= m;i ++) {
   for (int j = 1;j <= n;j ++) {
    scanf ("%d",&mat[i][j]);
   }
  }
  int ans = 0;
  memset(h,0,sizeof(h));
  for(int i = 1;i <= m; i++){
   for(int j = 1; j <= n; j++){
    if(mat[i][j] == 1)
     h[j]++;
    else
     h[j] = 0;
   }
   h[0] = h[n + 1] = -1;
   for(int j = 1;j <= n; j++){
    int k = j;
    while(h[j] <= h[k - 1])
     k = l[k - 1];
    l[j] = k;
   }
   for(int j = n;j >= 1;j--){
    int k = j;
    while(h[j] <= h[k + 1])
     k = r[k + 1];
    r[j] = k;
   }
   for(int j = 1; j <= n; j++){
    if(ans < h[j] * (r[j] - l[j] + 1))
     ans = h[j] * (r[j] - l[j] + 1);
   }
  } 
  cout << ans << endl; 
 }
 return 0;
}


分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP