Pagini recente » Cod sursa (job #2123413) | Cod sursa (job #2256529) | Cod sursa (job #1364388) | Cod sursa (job #1081799) | Cod sursa (job #3347776)
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 205;
int matrix[NMAX][NMAX];
int heights_up_down[NMAX][NMAX], heights_down_up[NMAX][NMAX];
int max_up_down[NMAX], max_down_up[NMAX], next_left[NMAX], next_right[NMAX];
void compute_heights(int n, int m) {
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (matrix[i][j] == 1)
heights_up_down[i][j] = 0;
else
heights_up_down[i][j] = heights_up_down[i - 1][j] + 1;
}
}
for (int j = m; j >= 1; j--) {
for (int i = n; i >= 1; i--) {
if (matrix[i][j] == 1)
heights_down_up[i][j] = 0;
else
heights_down_up[i][j] = heights_down_up[i + 1][j] + 1;
}
}
}
void compute_left(int n, int v[]){
stack<int> st;
for(int i = 1; i <= n; i++){
while(!st.empty() && v[st.top()] >= v[i]){
st.pop();
}
if(st.empty()) next_left[i] = 0;
else next_left[i] = st.top();
st.push(i);
}
}
void compute_right(int n, int v[]){
stack<int> st;
for(int i = n; i >= 1; i--){
while(!st.empty() && v[st.top()] >= v[i]){
st.pop();
}
if(st.empty()) next_right[i] = n + 1;
else next_right[i] = st.top();
st.push(i);
}
}
void compute_max_rectangle(int n, int m, int a[NMAX][NMAX]) {
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++)
// printf("%d", a[i][j]);
// printf("\n");
// }
for (int i = 1; i <= n; i++) {
compute_left(m, a[i]);
compute_right(m, a[i]);
for (int j = 1; j <= m; j++) {
max_up_down[i] = a[i][j] * (next_right[j] - next_left[j] - 1);
}
}
// for (int i = 1; i <= n; i++) {
// printf("%d\n", max_up_down[i]);
// }
}
void compute_results(int n, int m) {
compute_heights(n, m);
compute_max_rectangle(n, m, heights_up_down);
}
char line[NMAX];
int main() {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", &line);
for (int j = 0; j < m; j++)
matrix[i][j + 1] = line[j] - '0';
}
compute_results(n, m);
return 0;
}