P9904 [COCI 2023/2024 #1] Labirint 题解

· · 题解

注意到，一个点到一个点经过的颜色总数等两点互换的颜色总数。当只保留某些颜色时的图时，问题转换成了可达性问题，可以用并查集做。而所有保留某些颜色的图总共有 2^4=16 种，即每个颜色存在保留和不保留两种状态，一共四种颜色。最后在可达的图中，比较使用颜色最小值，输出即可。可以用状压优化，时间复杂度 \Theta(16nm \log{(nm)}+q)，其实并查集两种优化都加（路径压缩，按秩合并）还可以做到 \Theta(16nm \alpha{(nm)}+q)，但是实际上差不多，目前本题最优解。

放上你们心心念念的代码：

路径压缩：

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define mk(i,j) (((i)-1)*m+(j))
using namespace std;
const int maxn=1e4+10,maxm=1e6+10,mod=1e9+7;

int n,m,q,cb[maxn],cl[10]={'P','C','Z','N'},f[20][maxn];
vector<pii> e[20];
int find(int *f,int x){return f[x]==x?x:f[x]=find(f,f[x]);}

signed main(){
//  freopen("maze.in","r",stdin);
//  freopen("maze.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    rep(i,1,n) rep(j,1,m-1){
        char c;
        cin>>c;
        rep(k,0,3) if(c==cl[k]) e[1<<k].push_back({mk(i,j),mk(i,j+1)});
    }
    rep(i,1,n-1) rep(j,1,m){
        char c;
        cin>>c;
        rep(k,0,3) if(c==cl[k]) e[1<<k].push_back({mk(i,j),mk(i+1,j)});
    }
    rep(i,1,n*=m) f[0][i]=i;
    rep(sub,1,15){
        int lb=sub&-sub,ls=sub-lb;
        cb[sub]=cb[ls]+1;
        rep(i,1,n) f[sub][i]=f[ls][i];
        rep(i,0,e[lb].size()-1) f[sub][find(f[sub],e[lb][i].fi)]=find(f[sub],e[lb][i].se);
    }
    cin>>q;
    rep(i,1,q){
        int x1,y1,x2,y2,a,b,ans=5;
        cin>>x1>>y1>>x2>>y2,a=mk(x1,y1),b=mk(x2,y2);
        rep(i,1,15) if(find(f[i],a)==find(f[i],b)) ans=min(ans,cb[i]);
        cout<<ans<<'\n';
    }
    return 0;
}

两种优化：

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define mk(i,j) (((i)-1)*m+(j))
using namespace std;
const int maxn=1e4+10,maxm=1e6+10,mod=1e9+7;

int n,m,q,cb[maxn],cl[10]={'P','C','Z','N'},f[20][maxn],sz[20][maxn];
vector<pii> e[20];
int find(int *f,int x){return f[x]==x?x:f[x]=find(f,f[x]);}

signed main(){
//  freopen("maze.in","r",stdin);
//  freopen("maze.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    rep(i,1,n) rep(j,1,m-1){
        char c;
        cin>>c;
        rep(k,0,3) if(c==cl[k]) e[1<<k].push_back({mk(i,j),mk(i,j+1)});
    }
    rep(i,1,n-1) rep(j,1,m){
        char c;
        cin>>c;
        rep(k,0,3) if(c==cl[k]) e[1<<k].push_back({mk(i,j),mk(i+1,j)});
    }
    rep(i,1,n*=m) f[0][i]=i,sz[0][i]=1;
    rep(sub,1,15){
        int lb=sub&-sub,ls=sub-lb;
        cb[sub]=cb[ls]+1;
        rep(i,1,n) f[sub][i]=f[ls][i],sz[sub][i]=sz[ls][i];
        rep(i,0,e[lb].size()-1){
            int x=find(f[sub],e[lb][i].fi),y=find(f[sub],e[lb][i].se);
            if(sz[sub][x]>sz[sub][y]) swap(x,y);
            f[sub][x]=y,sz[sub][y]+=sz[sub][x];
        }
    }
    cin>>q;
    rep(i,1,q){
        int x1,y1,x2,y2,a,b,ans=5;
        cin>>x1>>y1>>x2>>y2,a=mk(x1,y1),b=mk(x2,y2);
        rep(i,1,15) if(find(f[i],a)==find(f[i],b)) ans=min(ans,cb[i]);
        cout<<ans<<'\n';
    }
    return 0;
}