自动搬运

查看原文

来自洛谷，原作者为

	luan341502 AFOed

搬运于2025-08-24 22:50:21，当前版本为作者最后更新于2023-09-18 23:25:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛时交了八发才过，少考虑了一种情况。

考虑将每个点对应能到的点连起来，这样就构成了一张图（如果对于不满足题目条件的点不进行连边的话，就无法构成一棵基环树）。

观察可以发现只有两种情况满足题目要求：

1. 整个图构成一个环，此时从任意点出发都能经过所有点。

2. 从一个点出发到达一个环，最终遍历完整个图。

对于两种情况分别判断，用并查集记录即可。

1. 所有点在一个并查集内就满足情况。

2. 只有一个点入度为零，否则一定不满足情况。统计入度情况进行判断即可。

由于 $n \times m \leq 10^5$，考虑使用将矩阵映射为直线的做法，这样只需开长度为 $10^5$ 的一维数组。

#include<bits/stdc++.h>
using namespace std;
int n,m;
string str[100005];
int fa[100005],d[100005];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y,int x_,int y_){
	int s1=(x-1)*m+y,s2=(x_-1)*m+y_;
	int u=find(s1),v=find(s2);
	if(u!=v) fa[v]=u;
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n*m;i++){
		fa[i]=i;
		d[i]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>str[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);
			int ch=(int)str[i][j-1],p,q;
			if(ch==117) p=i-x,q=j;
			else if(ch==100) p=i+x,q=j;
			else if(ch==108) p=i,q=j-x;
			else p=i,q=j+x;
			if(p<1||q<1||p>n||q>m) continue;
			merge(i,j,p,q);
			d[(p-1)*m+q]++;
		}
	}
	int x=find(1),cnt=n*m;
	for(int i=2;i<=cnt;i++){
		if(find(i)!=x){
			puts("No");
			return;
		}
	}
	int res=0;
	for(int i=1;i<=cnt;i++){
		if(!d[i]) res++;
		if(res>1){
			puts("No");
			return;
		}
	}
	puts("Yes");
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}