Pagini recente » Cod sursa (job #3124327) | Cod sursa (job #543841) | Cod sursa (job #156834) | Cod sursa (job #1657000) | Cod sursa (job #1730952)
#include <fstream>
#include <math.h>
using namespace std;
string problemName = "bmatrix";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());
int rows, columns, answer;
const int Nmax = 205;
bool v[Nmax][Nmax];
int maximumHeight[Nmax][Nmax], maximumDepth[Nmax][Nmax];
int firstSmallerLeft[Nmax][Nmax], firstSmallerRight[Nmax][Nmax];
int bestRectangleAbove[Nmax], bestRectangleBelow[Nmax];
int stack[Nmax];
void read(){
fin>>rows>>columns;
string s;
int i, j;
for(i = 1;i <= rows;i++){
fin>>s;
for(j = 0;j < columns;j++){
v[i][j+1] = s[j] - '0';
}
}
}
void print(){
fout<<answer;
}
void printArray(int aux[][Nmax]){
int i, j;
for(i = 1;i <= rows;i++){
for(j = 1;j <= columns;j++){
fout<<aux[i][j]<<' ';
}
fout<<'\n';
}
}
void getMaximumHeight(){
int i, j;
for(i = 1;i <= rows;i++){
for(j = 1;j <= columns;j++){
if(v[i][j] == 0){
maximumHeight[i][j] = 1 + maximumHeight[i-1][j];
}else{
maximumHeight[i][j] = 0;
}
}
}
}
void getFirstSmallerHeightLeft(){
int i, j, last;
for(i = 1;i <= rows;i++){
last = 0;
for(j = 1;j <= columns;j++){
while(last > 0 && maximumHeight[i][j] <= maximumHeight[i][stack[last]]){
last--;
}
if(last == 0){
firstSmallerLeft[i][j] = 0;
}else{
firstSmallerLeft[i][j] = stack[last];
}
stack[++last] = j;
}
}
}
void getFirstSmallerHeightRight(){
int i, j, last;
for(i = 1;i <= rows;i++){
last = 0;
for(j = columns;j >= 1;j--){
while(last > 0 && maximumHeight[i][j] <= maximumHeight[i][stack[last]]){
last--;
}
if(last == 0){
firstSmallerRight[i][j] = columns+1;
}else{
firstSmallerRight[i][j] = stack[last];
}
stack[++last] = j;
}
}
}
void getBestRectangleAbove(){
int i, j;
for(i = 1;i <= rows;i++){
for(j = 1;j <= columns;j++){
bestRectangleAbove[i] = max(bestRectangleAbove[i], maximumHeight[i][j] * (firstSmallerRight[i][j] - firstSmallerLeft[i][j] - 1));
}
}
for(i = 1;i <= rows;i++){
bestRectangleAbove[i] = max(bestRectangleAbove[i], bestRectangleAbove[i-1]);
}
}
void solveAbove(){
getMaximumHeight();
getFirstSmallerHeightLeft();
getFirstSmallerHeightRight();
getBestRectangleAbove();
}
void getMaximumDepth(){
int i, j;
for(i = rows;i >= 1;i--){
for(j = 1;j <= columns;j++){
if(v[i][j] == 0){
maximumDepth[i][j] = 1 + maximumDepth[i+1][j];
}else{
maximumDepth[i][j] = 0;
}
}
}
}
void getFirstSmallerDepthLeft(){
int i, j, last;
for(i = 1;i <= rows;i++){
last = 0;
for(j = 1;j <= columns;j++){
while(last > 0 && maximumDepth[i][j] <= maximumDepth[i][stack[last]]){
last--;
}
if(last == 0){
firstSmallerLeft[i][j] = 0;
}else{
firstSmallerLeft[i][j] = stack[last];
}
stack[++last] = j;
}
}
}
void getFirstSmallerDepthRight(){
int i, j, last;
for(i = 1;i <= rows;i++){
last = 0;
for(j = columns;j >= 1;j--){
while(last > 0 && maximumDepth[i][j] <= maximumDepth[i][stack[last]]){
last--;
}
if(last == 0){
firstSmallerRight[i][j] = columns+1;
}else{
firstSmallerRight[i][j] = stack[last];
}
stack[++last] = j;
}
}
}
void getBestRectangleBelow(){
int i, j;
for(i = 1;i <= rows;i++){
for(j = 1;j <= columns;j++){
bestRectangleBelow[i] = max(bestRectangleBelow[i], maximumDepth[i][j] * (firstSmallerRight[i][j] - firstSmallerLeft[i][j] - 1));
}
}
for(i = rows;i >= 1;i--){
bestRectangleBelow[i] = max(bestRectangleBelow[i], bestRectangleBelow[i+1]);
}
}
int mergeRectangles(){
int i, currentBest = 0;
for(i = 1;i < rows;i++){
currentBest = max(currentBest, bestRectangleAbove[i]+bestRectangleBelow[i+1]);
}
return currentBest;
}
void solveBelow(){
getMaximumDepth();
getFirstSmallerDepthLeft();
getFirstSmallerDepthRight();
getBestRectangleBelow();
}
void solve(){
solveAbove();
solveBelow();
answer = max(answer, mergeRectangles());
}
void rotateArray(){
int i, j;
bool aux[Nmax][Nmax];
for(i = 1;i <= columns;i++){
for(j = 1;j <= rows;j++){
aux[i][j] = v[j][columns-i+1];
}
}
for(i = 1;i <= columns;i++){
for(j = 1;j <= rows;j++){
v[i][j] = aux[i][j];
}
}
swap(rows, columns);
}
void resetAll(){
int i, j;
for(i = 1;i <= rows;i++){
for(j = 1;j <= columns;j++){
maximumHeight[i][j] = 0;
maximumDepth[i][j] = 0;
firstSmallerLeft[i][j] = 0;
firstSmallerRight[i][j] = 0;
}
bestRectangleAbove[i] = 0;
bestRectangleBelow[i] = 0;
}
}
void init(){
read();
solve();
resetAll();
rotateArray();
solve();
print();
}
int main(){
init();
return 0;
}