题解 P3684 【[CERC2016]机棚障碍 Hangar Hurdles】

· · 题解

基础图论作业题。感觉难度不及黑？

可能是我之前写过这玩意或者现在的做法相对简单很多。

题意

给定一个长宽均为 n 的黑白矩阵，你需要回答 q 组询问：

给定起点坐标和终点坐标，你有一个初始中心在起点，边长为 x 的正方形。在“存在一条从起点到终点的路径，使得正方形的中心在路径上移动时不碰到任何黑格子”的条件下，求出最大可能的奇整数 x。如果不存在，输出 0。

做法

感性理解有“路径上最宽的部分影响答案”，于是可以想到瓶颈路。

在这里给出一个复杂度较劣，但是相当好写的离线瓶颈路做法（基于 Kruskal，但是不需要用到 Kruskal 重构树相关知识）：

  1. 将边按边权排序。

  2. 维护 set<int>s[N]，对于每个询问 x_i,y_i，把询问编号 i 插入对应的 set 中。

  3. 按照边权顺序处理每一条边。对于一条边 x\xleftrightarrow w y，如果 x,y 不在一个连通块内，启发式合并两个集合 s_x,s_y。如果 s_x,s_y 中有相同元素，将两个元素同时删除，并标记该元素对应询问答案为 w。最后合并 x,y 所在连通块。

时间复杂度 O(q\log m\log q)，m 为边数，q 为询问数。复杂度瓶颈为启发式合并和 set 的 insert 操作。

回到这个问题。首先用朴素的 DP 求出一个坐标可以拓展的最大正方形的边长 w_{i,j}。（左上，右上，左下，右下直接 DP，然后合并）然后套用上面的方法，将所有点按照 w 降序排序，然后依次如上处理，向四个方向合并即可。

时间复杂度 O(q\log n^2\log q)，较题解区的 O(n^2\log n^2) 劣。但是因为本题中 q<n^2 且开了 4s，所以实际上跑起来也不会超时，但是好像卡到时限了。

代码

变量和上面数组对应。

没有刻意缩减代码，代码比题解代码短不少（很多重复），且保留了可读性。

//P3684 AC Code
//written by Loser_King(159686)
//C++14 (GCC 9) | 1.94KB | 7.93s | 112.96MB
#include<bits/stdc++.h>
#define ord(x,y) (((x)-1)*n+(y))
#define getx(k) (((k)-1)/n+1)
#define gety(k) (((k)-1)%n+1)
using namespace std;
int const N=1010,K=N*N,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int n,q,w[N][N],ul[N][N],ur[N][N],dl[N][N],dr[N][N],f[K],ans[K];
char a[N][N];
set<int>s[K];
pair<int,int>p[K];
int find(int x){
    return x^f[x]?f[x]=find(f[x]):x;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n*n;i++)
        f[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='.')
                ul[i][j]=min(ul[i-1][j-1],
                    min(ul[i][j-1],ul[i-1][j]))+1;
    for(int i=1;i<=n;i++)
        for(int j=n;j>=1;j--)
            if(a[i][j]=='.')
                ur[i][j]=min(ur[i-1][j+1],
                    min(ur[i-1][j],ur[i][j+1]))+1;
    for(int i=n;i>=1;i--)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='.')
                dl[i][j]=min(dl[i+1][j-1],
                    min(dl[i+1][j],dl[i][j-1]))+1;
    for(int i=n;i>=1;i--)
        for(int j=n;j>=1;j--)
            if(a[i][j]=='.')
                dr[i][j]=min(dr[i+1][j+1],
                    min(dr[i+1][j],dr[i][j+1]))+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            p[ord(i,j)]={w[i][j]=min(ul[i][j],min(ur[i][j],
                min(dl[i][j],dr[i][j])))*2-1,ord(i,j)};
    sort(p+1,p+1+n*n,greater<pair<int,int> >());
    cin>>q;
    for(int i=1;i<=q;i++){
        int ax,ay,bx,by;
        cin>>ax>>ay>>bx>>by;
        s[ord(ax,ay)].insert(i);
        s[ord(bx,by)].insert(i);
    }
    for(int i=1;i<=n*n;i++){
        int x=getx(p[i].second),y=gety(p[i].second),
            fa=find(p[i].second),k=p[i].first;
        if(a[x][y]=='#')
            continue;
        for(int j=0;j<4;j++){
            int tx=x+dx[j],ty=y+dy[j],tfa=find(ord(tx,ty));
            if(tx<1||ty<1||tx>n||ty>n||w[tx][ty]<w[x][y]||fa==tfa)
                continue;
            int fx=fa,fy=tfa;
            if(s[fx].size()>s[fy].size())
                swap(fx,fy);
            f[fx]=fa=fy;
            for(int w:s[fx])
                if(s[fy].count(w))
                    ans[w]=k,s[fy].erase(w);
                else
                    s[fy].insert(w);
            s[fx].clear();
        }
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}