首页 > 代码库 > [Jobdu] 题目1497：面积最大的全1子矩阵
[Jobdu] 题目1497：面积最大的全1子矩阵
- 题目描述：
在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。
- 输入：
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。
- 输出：
对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。
- 样例输入：
2 20 00 04 40 0 0 00 1 1 00 1 1 00 0 0 0
- 样例输出：
04
可以将上述问题转化为求直方图中最大的矩形的面积，将原矩阵中的每一行视为一个直方图，对于每一行中的每一列的值为该行之上的1的个数，下面分别利用直方图的算法来求解每一行中的最大值，然后求出全局最大值。代码如下：
1 #include <iostream> 2 #include <stack> 3 #include <cstdio> 4 using namespace std; 5 6 int m, n; 7 int a[1000][1000]; 8 int b[2][1001]; 9 int f = 0;10 11 int getMax() {12 stack<int> s;13 b[f][n] = 0;14 int max = 0, tmp;15 for (int i = 0; i <= n; ++i) {16 if (s.empty() || b[f][s.top()] < b[f][i]) {17 s.push(i);18 } else {19 int idx = s.top();20 s.pop();21 tmp = b[f][idx] * (s.empty() ? i : i - s.top() - 1);22 max = (max > tmp) ? max : tmp;23 --i;24 }25 }26 return max;27 }28 29 void getRes() {30 int max = getMax(), tmp;31 ++f; f %= 2;32 for (int i = 1; i < m; ++i) {33 for (int j = 0; j < n; ++j) {34 b[f][j] = (a[i][j] == 0) ? 0 : b[(f+1)%2][j] + 1;35 }36 tmp = getMax();37 ++f; f %= 2;38 max = (max > tmp) ? max : tmp;39 }40 cout << max << endl;41 }42 43 int main() {44 //freopen("1497.in", "r", stdin);45 while (cin >> m >> n) {46 f = 0;47 for (int i = 0; i < m; ++i) {48 for (int j = 0; j < n; ++j) {49 cin >> a[i][j];50 if (i == 0)51 b[0][j] = a[0][j];52 }53 }54 getRes();55 }56 return 0;57 }58 59 /**************************************************************60 Problem: 149761 User: hupo25062 Language: C++63 Result: Accepted64 Time:800 ms65 Memory:5432 kb66 ****************************************************************/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。