题目链接: link. 题目： 题意：在n行m列网格，输入r-右，l-左，u-上，d-下，的字符，在之后n行分别是每个坐标位置 的移动的步数。问是否存在合适的点，该点一条路径能够经过所有点恰好一次。
思路：实际上这是一道图题而且每个点的出度为1或者0（0情况是移动超出网格) 不妨对每个坐标点位置用一个数字（点）表示,（i，j）可表示点（i-1）*m+j; 如（6,2）对应 点为52(9行10列)。 如果存在该点，前提条件是图是连通图。 如果是连通图，只要考虑能否一点经过剩下所有点。由于出度一定是1或0该图很特殊。 只要入度为0只能有一个（入度为0的点该起点），或者没有（一个环）。一旦多于1个就不存在（假如可能会有两个以上起点，很显然这个两个起点各自不能到达对方，所以不存在）。
用并查集判断图的连通性。 后面入度判断实现较容易。
#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 200005 int f[maxn]; char s[maxn]; int ru[maxn]; int n,m; void init(){ int sum =n*m; for(int i=1;i<=sum;i++) f[i]= i; return ; } int find(int x){ return x==f[x] ? x:f[x]=find(f[x]); } void merge(int a,int b){ int x= find(a); int y= find(b); if(x!=y) f[x]= y; return ; } int main (){ int T; cin>>T; while(T--){ cin>>n>>m; init(); memset(ru,0,sizeof(ru)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>s[m*(i-1)+j]; //cout<<s[n*(i-1)+j]; } //for(int i=1;i<=n*m;i++) // cout<<s[i]; cout<<endl; //cout<<n<<" "<<m<<endl; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int flag; cin>>flag; int a,b; a= (i-1)*m+j; int ti=i,tj=j; if(s[a]=='u') ti = i-flag; else if(s[a]=='d') ti = i+flag; else if(s[a]=='r') tj= j+flag; else if(s[a]=='l') tj=j-flag; //cout<<ti<<":"<<tj<<endl; if(ti<1||ti>n||tj>m||tj<1) continue; b=(ti-1)*m+tj; merge(a,b); ru[b]++; } int fa= find(1); int sum = n*m; int flag =1; for(int i=1;i<=sum;i++) if(find(i)!=fa){ flag=0; break; } if(flag==0){ cout<<"No"<<endl; } else { int ans= 0; for(int i=1;i<=sum;i++) { if(ru[i]==0) ans++; if(ans>=2) break; } if(ans>=2) cout<<"No"<<endl; else cout<<"Yes"<<endl; } } }