题目描述:有一个n*m的方格,给定起始位置,‘#’表示不可走‘ .’表示可走 超出范围的按x%n,y%m 判定是‘#’ 还是‘.' 判断是否可走 , 问是否可以走到无穷远处
分析:如果出了范围后走到了没出范围的点(x%n,y%m 相等)那么 肯定可以循环下去 也就是无穷远,因为dfs要标记走过的点 防止下次走,所以不能用是否走过来判断,
最好设置一个记录看看该点两次走分别对应哪个点(这么简单竟然想了这么。。。。。。。。。。。)
ac代码:
#include<bits/stdc++.h>usingnamespacestd;constintMAX=1600;charmapp[MAX][MAX];intvis[MAX][MAX];intn,m;intdira[4][2]={{1,0},{0,1},{-1,0},{0,-1}};pair<int,int>near[MAX][MAX];intflag=0;voiddfs(intx,inty){// cout<<x<<' '<<y<<endl;// system("pause");// if(flag==1) return ;intx1=x,y1=y;while(x1<0) x1+=n;x1%=n;while(y1<0) y1+=m;y1%=m;if(vis[x1][y1]&&near[x1][y1]!=pair<int,int> (x,y)){cout<<"YES"<<endl;exit(0);}if(vis[x1][y1]||mapp[x1][y1]=='#') {// cout<<"FDS"<<endl;return;}vis[x1][y1]=1;near[x1][y1]=make_pair(x,y);for(inti=0;i<4;i++){dfs(x+dira[i][0],y+dira[i][1]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0);// freopen("1.txt","r",stdin);cin>>n>>m;intx,y;for(inti=0;i<n;i++)for(intj=0;j<m;j++){cin>>mapp[i][j];if(mapp[i][j]=='S'){x=i;y=j;}}memset(vis,0,sizeof(vis));dfs(x,y);cout<<"NO"<<endl;}