Second Large Rectangle（悬线法）

【题意】

【代码】

不知道怎么贴代码

#include <iostream>
#include <algorithm>
using namespace std;
const int Max = 3005;
int ves[Max][Max], up[Max][Max], Left[Max][Max], Right[Max][Max];
int  temp2 = 0,mx=0;
char s[Max][Max];
 
int main()
{
    int N, M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) scanf("%s",s[i]+1);
    for(int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) {
            ves[i][j]=s[i][j]-'0';
            if(ves[i][j])
            {
                Left[i][j] = Right[i][j] = j;    
                up[i][j] = 1;    
            }
        }
 
    for (int i = 1; i <= N; i++)
        for (int j = 2; j <= M; j++)
            if (ves[i][j] == ves[i][j - 1]&&ves[i][j] ==1)
                Left[i][j] = Left[i][j - 1];    //ÊÇ£¬Ôò
 
    for (int i = 1; i <= N; i++)
        for (int j = M - 1; j > 0; j--)
            if (ves[i][j] ==ves[i][j + 1]&&ves[i][j]==1)
                Right[i][j] = Right[i][j + 1];
     int mx=0;
     int x1,y1,x2,y2;
     int l,r;
    for(int i = 1;i <= N; i++)
        for (int j = 1; j <= M; j++) {
            if (i > 1 && ves[i][j] == ves[i - 1][j]&&ves[i][j]==1) {    
                Left[i][j] = max(Left[i][j], Left[i - 1][j]);
                Right[i][j] =min(Right[i][j], Right[i - 1][j]);
                up[i][j] = up[i - 1][j] + 1;
            }
 
            int A_instance = Right[i][j] - Left[i][j] + 1;    //¼ÆË㳤¶È
            int x11=i;
            int y11=Left[i][j];
            int x22=i-up[i][j]+1;
            int y22=Right[i][j];
            if(A_instance * up[i][j]>=temp2&&(x11!=x1||y11!=y1||x22!=x2||y22!=y2)){
                temp2=A_instance * up[i][j];
                x1=x11;
                y1=y11;
                x2=x22;
                y2=y22;
                int d1=y2-y1+1;
                int d2=x1-x2+1;
                mx=max(mx,temp2-d1);
                mx=max(mx,temp2-d2);
                //printf("i:%d j:%d temp:%d\n",i,j,temp2);
            }
        }
 
 
        for(int i = 1;i <= N; i++)
        for (int j = 1; j <= M; j++) {
            int A_instance = Right[i][j] - Left[i][j] + 1;    //¼ÆË㳤¶È
            int x11=i;
            int y11=Left[i][j];
            int x22=i-up[i][j]+1;
            int y22=Right[i][j];
            //prin(x11,y11,x22,y22);
            if(A_instance * up[i][j]>=mx&&(x11!=x1||y11!=y1||x22!=x2||y22!=y2)){
                mx=A_instance * up[i][j];
                //prin(x11,y11,x22,y22);
            }
        }
 
         printf("%d\n",mx);
         return 0;
}
【题目】

链接：https://ac.nowcoder.com/acm/contest/882/H
来源：牛客网
 

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