LuoguP9641题解

luan341502 · 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;
}