链接:https://ac.nowcoder.com/acm/contest/882/H
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
Given a N×MN×M binary matrix. Please output the size of second large rectangle containing all "1""1".
Containing all "1""1" means that the entries of the rectangle are all "1""1".
A rectangle can be defined as four integers x1,y1,x2,y2x1,y1,x2,y2 where 1≤x1≤x2≤N1≤x1≤x2≤N and 1≤y1≤y2≤M1≤y1≤y2≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2x1≤x≤x2 and y1≤y≤y2y1≤y≤y2. If all of the cell in the rectangle is "1""1", this is a valid rectangle.
Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.
输入描述:
The first line of input contains two space-separated integers N and M.
Following N lines each contains M characters cijcij.
1≤N,M≤10001≤N,M≤1000
N×M≥2N×M≥2
cij∈"01"cij∈"01"
输出描述:
Output one line containing an integer representing the answer. If there are less than 2 rectangles containning all "1""1", output "0""0".
示例1
输入
1 2
01
输出
0
示例2
输入
1 3
101
输出
1
题意:求第二大全1矩阵
题解:用dp[i][j]表示这个位置,往上延伸最多有多少个连续的1,结构体存的是矩形的高 和 宽的左边坐标,然后暴力一行一行找~~
感觉会超时,结果没超时,还贼快~~
上代码:(此代码max1是第一大,max2是第二大,所以第一大,第二大都能求~~哈哈~~)
#include <iostream>
using namespace std;
const int MAX = 1e3+400;
int max1,max2,top;//max1是第一大的值,max2是第二大的值
struct hh{
int l,h;
hh(int _l=0,int _h=0):l(_l),h(_h){}
}q[MAX];
int dp[MAX][MAX],s[MAX][MAX];
void update(int x){
if(x>=max1){
max2=max1;
max1=x;
}
else if(x>max2){
max2=x;
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n;i++){
for (int j = 1; j <= m;j++){
scanf("%1d",&dp[i][j]);
s[i][j]=dp[i][j];
dp[i][j]+=dp[i][j]*dp[i-1][j];//保存向上延伸最多有多少个1
}
}
for (int i = 1; i <= n;i++){
top=0;
for (int j = 1; j <= m;j++){
if(s[i][j]==0) top=0;//有一个是0,就要重新开始找,前面无法再包括进去,只能往后找
else{
int tmp=j;
while(q[top].h>dp[i][j]&&top) tmp=q[top--].l;//找到宽符合是全1矩阵的位置
if(q[top].h!=dp[i][j]) q[++top]=hh(tmp,dp[i][j]);
for (int k = 1; k <= top;k++){
update(q[k].h*(j-q[k].l+1));//更新最大、第二大的值
}
}
}
}
printf("%d\n",max2);//输出第二大的值
return 0;
}