自动搬运

查看原文

来自洛谷，原作者为

	STARSczy 不是奶龙，原神启动，加油

搬运于2025-08-24 22:52:54，当前版本为作者最后更新于2024-02-28 16:00:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到，一个点到一个点经过的颜色总数等两点互换的颜色总数。当只保留某些颜色时的图时，问题转换成了可达性问题，可以用并查集做。而所有保留某些颜色的图总共有 $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;
}