最大红矩形

最大红矩形

时间限制：10 sec

空间限制：256 MB

问题描述

有一个 n*m 的棋盘，棋盘上的每个点都是红的或绿的。

你需要找出一个面积最大的矩形区域，使得其中没有绿的格子。

输入格式

第一行 2 个正整数 n,m，描述棋盘尺寸。

接下来 n 行描述这个棋盘，每行 m 个字符，每个字符为 . 或 X，其中 . 表示这个位置是红色的，X 表示这个位置是绿色的。

输格式

一行一个整数，表示最大面积。

样例输入

样例输

样例解释

以第 3 行第 3 列的方格为左上角，第 4 行第 5 列的方格为右下角的矩形区域是全红的矩形中面积最大的。

数据范围

对于30%的数据，n,m<=100；

对于60%的数据，n,m<=400；

对于85%的数据，n,m<=1,000；

对于 100% 的数据，n,m<=1,500。

提示

[这道题与“直方图最大面积”一题有什么关系呢？]

代码:

#include<iostream> #include<stack>

using namespace std;

/*此题可用直方图最大面积的题目中的方法来计算最大红矩形面积

  即将此题中的数据构造为直方图，例如.X.

                                    ...

...

  则(0,0)的直方图高度为1,(0,1)为0,(1,0)为2,(1,1)为1(当前行'.'减去上一个'X'所在行数所形成的高度)

*/

int main()

{

int n, m;

cin >> n >> m;//读入行数和列数

stack<int>* N_X = new stack<int>[m];

/*新建一组堆栈，用于构造当前行中某列所构造的直方图的高度

  堆栈顶部存有当前列最近遇到的'X’字符所在的行数n'，当读入字符为'.'时，使用当前行数 n减去n'即可得到用于构造当前行中某列所构造的直方图的高度

*/

for (int i = 0; i < m; i++)

N_X[i].push(-1);//栈的初始化，将-1压入栈(例如第0行高度为1，0-(-1)=1)

stack<int> TEMP;//初始栈，用于上面所获得的存储直方图的高度

char** matrix = new char*[n];//建立一个char型n*m的二维矩阵并初始化

for (int i = 0; i < n; i++)

{

matrix[i] = new char[m];

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)  

{

cin >> matrix[i][j];//将数据读入二维矩阵中

//'.'表示红，'X'表示绿

if (matrix[i][j] == '.')//若遇到红点，则直接将该行该列的直方图的高度压入初始栈TEMP中

{

int height = i - N_X[j].top();//获得直方图高度

TEMP.push(height);

}

else if (matrix[i][j] == 'X')//若遇到绿点，则将高度0压入栈中，并向N_X栈压

入当前列中X所处的行数

{

TEMP.push(0);

N_X[j].push(i);

}

}

TEMP.push(0);/*当用于在下面中打印输出每一行的直方图高度，若无此句，则有可能会将多行的直方图高度加在一起进行输出

例如

   XXXXX

   .X...

   .....

   由于栈是先进后出，故下面的代码会认为最大高度为8(即从

第20个~13个元素均为直方图面积，高度为1)

   而正确的答案是6

*/

}

//以下为原直方图最大面积中的源代码

stack<int> H;//用于存储高度

stack<int> N;//用于存储下标

int maxRect = 0;

int tempRect = 0;

H.push(-1);//压入一个哨位节点，用于卡位

int temp;//用于读取最初的数据

int num = n * m + n;//由于每一行多一个0，所需读取的数目为n*m+n

for (int k = 0; k < num; k = k)

{

if (N.empty() || H.top() <= TEMP.top())//若TEMP中栈顶所存在的直方图的高度比H中栈顶的高度小，说明可以压入栈，即点是普通点，非Low或High点（卡位点)

{

H.push(TEMP.top());

N.push(k);

TEMP.pop();

k++;

}

else//若H.top() > TEMP.top()，说明遇到了卡位点（High点）,此时应将H和N中的元素弹出一个（是否弹出多个等待下一轮循环再进行检测)

{

temp = N.top();

N.pop();

if (!N.empty())

{

tempRect = (k - N.top() - 1)*H.top();//需要先弹出一个N中的栈顶元素然

后再乘以H.to

p()，因为原先

} N中栈顶元素的左边可能存在应该加上

的直方图面积

//具体原因请见附件Excel演示

else//如果弹出一个元素后为空，说明N原先栈顶中左边的直方图面积为

H.t

op()*N.to

p()，即原先N栈顶元素左边直方图面积的长为N.top一直到0

{

tempRect = k * H.top();

}

H.pop();

if (tempRect > maxRect)

}

} maxRect = tempRect;

while (!N.empty())//当遍历完所有直方图时，需要再次清空N，若N中存在元素，则有可能所获得错误的直方图面积最大值

   //以下代码类似于上面for循环中的else代码

{

temp = N.top();

N.pop();

if (!N.empty())

{

tempRect = (num - N.top() - 1)*H.top();//需要先弹出一个N中的栈顶元素然后再

乘以H.top()，因为原先N中栈顶元素的左边可能存在应该加上的直方图面积

//具体原因请见附件Excel演示

}

else//如果弹出一个元素后为空，说明N原先栈顶中左边的直方图面积为H.top()*(N.top()-1)，即原先N栈顶元素左边直方图面积的长为N.top一直到0

{

tempRect = num * H.top();

}

H.pop();

if (tempRect > maxRect)

maxRect = tempRect;

}

cout << maxRect << endl;

return 0;

}