10667 - Largest Block Solution by using Histogram Area Algorithm
10667 - Largest Block
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
using namespace std;
bool matrix[100][100];
int calculate_max_histogram_area(int *arr,int len){
stack<int> st;
int i, max, temp,temp_sum,cur_index,sum;
temp = 0;
max = 0;
temp_sum = 0;
for (i = 0; i< len; i++){
if (arr[i]>0 && arr[i] >= temp){
temp = arr[i];
st.push(i);
}
else{
temp = arr[i];
while (true){
if (st.empty())
break;
cur_index = st.top();
if (arr[cur_index] == temp)
break;
st.pop();
sum = arr[cur_index] * (i - cur_index);
if (sum > max){
max = sum;
}
}
if (i < len && arr[i]>0)
st.push(i);
}
}
while (!st.empty()){
cur_index = st.top();
st.pop();
sum = arr[cur_index] * (i - cur_index);
if (sum > max){
max = sum;
}
}
return max;
}
int calculate_max_sub_matrix(int n){
int temp[100],i,j,k,temp_sum,max;
max = 0;
for (i = 0; i < n; i++){
fill(temp, temp + n, 0);
for (j = i; j < n; j++){
for (k = 0; k < n; k++){
if (matrix[j][k]){
temp[k]++;
}else{
temp[k] = 0;
}
}
temp_sum = calculate_max_histogram_area(temp, n);
if (temp_sum > max)
max = temp_sum;
}
}
return max;
}
int main(){
int n, i, j,test_case,x1,y1,x2,y2,b,temp,max;
cin >> test_case;
while (test_case--){
cin >> n>>b;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
matrix[i][j] = true;
if (b == 0){
max = n*n;
}
else{
while (b--){
cin >> x1 >> y1 >> x2 >> y2;
x1--;
y1--;
x2--;
y2--;
if (x1 > x2)
{
temp = x1;
x1 = x2;
x2 = temp;
}
if (y1 > y2)
{
temp = y1;
y1 = y2;
y2 = temp;
}
for (i = x1; i <= x2; i++)
for (j = y1; j <= y2; j++)
matrix[i][j] = false;
}
max= calculate_max_sub_matrix(n);
}
cout << max << endl;
}
return 0;
}
Comments
Post a Comment