A34897. 最大空白区
填空题
较难
知识点
题目描述
最大空白区
题目描述：
小明有一张矩形彩纸，他将彩纸均匀的画了N*M个小方格，有些小方格中被他画了小草，有些小方格是空白的，现小明想找出一片空白的方格，并且这片空白方格是最大的矩形。
现给出N和M的值，及每个方格的状态，被画小草的小方格用数字1表示，空白小方格用数字0表示，请帮小明找出最大矩形，并输出最大矩形由多少个小方格组成。
例如：N=4，M=5，
输入描述：
第一行输入两个正整数N和M（2≤N≤100，2≤M≤100），分别表示矩形彩纸方格的行数和列数，两个正整数之间以一个空格隔开
第二行开始，输入N行，每行M个正整数（正整数为1或者0），1表示小草，0表示空白，正整数之间一个空格隔开
输出描述：
输出一个整数，表示最大矩形由多少个小方格组成
样例输入：
4 5
1 1 0 0 0
1 0 1 0 0
0 0 0 1 1
0 0 0 1 0
样例输出：
6
参考答案
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N = 50;
int a[N][N];
int main() {
int n, m;
cin >> n >> m;
vector<vector<int> > gl(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if (a[i][j] == 0)
gl[i][j] = (j == 0 ? 1 : gl[i][j - 1] + 1);
}
}
int res = 0;
for (int j = 0; j < m; j++) {
vector<int> up(n, 0), down(n, 0);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && gl[st.top()][j] >= gl[i][j]) {
st.pop();
}
up[i] = st.empty() ? -1 : st.top();
st.push(i);
}
st = stack<int> ();
for (int i = n - 1; i >= 0; i--) {
while(!st.empty() && gl[st.top()][j] >= gl[i][j]) {
st.pop();
}
down[i] = st.empty() ? n : st.top();
st.push(i);
}
for (int i = 0; i < n; i++) {
int height = down[i] - up[i] - 1;
int area = height * gl[i][j];
res = max(res, area);
}
}
cout << res;
return 0;
}答案解析
评分标准：
4分：能正确输出第一组数据；
4分：能正确输出第二组数据；
4分：能正确输出第三组数据；
4分：能正确输出第四组数据；
4分：能正确输出第五组数据；
5分：能正确输出第六组数据。
上一题
下一题