题解 P3135 [USACO16JAN] Fort Moo P

· · 题解

我提供一种奇特的解法。

思路

暴力

枚举左上角坐标 (x_1,y_1) 和右上角坐标 (x_2,y_2) ，然后用二维前缀和判断一下有没有沼泽地，最后算一下面积，取最大值 就是答案。

时间复杂度 O(n^4) ，很明显会超时。

暴力代码：

#include<bits/stdc++.h>
using namespace std;
int sum[1145][1145];
int query(int x1,int y1,int x2,int y2){
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            sum[i][j]=-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1]+(s=='X');
        }
    }
    int ans=0;
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=m;y1++){
            for(int x2=x1;x2<=n;x2++){
                for(int y2=y1;y2<=m;y2++){
                    if(x1==x2&&y1==y2||query(x1,y1,x2,y1)||query(x1,y1,x1,y2)||query(x2,y1,x2,y2)||query(x1,y2,x2,y2))continue;
                    ans=max(ans,(x2-x1+1)*(y2-y1+1));
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

优化

我们可以枚举一个矩形的两列竖边 l_1 和 l_2 ，然后枚举所有在 [l_1,l_2] 间没有沼泽的横边，处理出来放到一个数组 q 里，如图

我们已经保证横边没有沼泽了，我们还需要找出两条横边，且两条横边夹着的两条竖边间没有沼泽，这样就能求出矩形的面积，然后取最大值。

问题是我们要找出两条横边并且是复杂度是 O(n) 的，怎么找？

定义两个指针 p_1 和 p_2 ，遍历一下数组 q ，令当前下标为 i ，让 p_2 等于 i ，如果 p_1 到 p_2 间有沼泽，令 p_1 等于 p_2 ，否则不变，计算此时的面积，取最大值。

关于这样做正确性证明：如果能走到 [p_1,p_2-1] 这里，那么 [p_1,p_2-1] 之间肯定是没有沼泽的，如果在 [p_1,p_2] 间发现了沼泽，那么沼泽肯定是在 [p_{2}-1,p_2] 之间的，也就是说区间想以 p_2 结尾，开头肯定只能从 p_2 开始。

时间复杂度 O(n^3) 。

代码

#include<bits/stdc++.h>
using namespace std;
int sum[1145][1145],q[1145];
int query(int x1,int y1,int x2,int y2){
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            sum[i][j]=-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1]+(s=='X');
        }
    }
    int ans=0;
    for(int l1=1;l1<=m;l1++){
        for(int l2=l1;l2<=m;l2++){
            int st,ed,p=0;
            for(int l3=1;l3<=n;l3++){
                if(!query(l3,l1,l3,l2))q[++p]=l3; //预处理合法的横边
            }
            if(p==0)continue;
            st=ed=q[1];
            ans=max(ans,(ed-st+1)*(l2-l1+1));
            for(int i=1;i<=p;i++){
                ed=q[i];
                if(query(st,l1,ed,l1)||query(st,l2,ed,l2)){
                    st=ed; //如果[p1,p2]有沼泽，那么p1=p2
                    ans=max(ans,(ed-st+1)*(l2-l1+1));
                }
                else ans=max(ans,(ed-st+1)*(l2-l1+1)); //否则可以走过来，不变
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}