#深搜#洛谷 1363 幻想迷宫

本文主要是介绍#深搜#洛谷 1363 幻想迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

图中是否出现走出边界的自环。

---

分析

广搜，深搜
用$v[x][y][0]$表示横坐标，$v[x][y][1]$表示纵坐标。$v[x][y][2]$表示是否走出边界，深搜过程比较简单，在此不多讲，不过为什么要这样做！（图片转自https://www.luogu.org/blog/GNAQ/solution-p1363），它会不断扩张，所以需要记录可能走出边界的横纵坐标。

---

代码

#include <iostream>
#define M 1500
using namespace std;
typedef short sr; bool flag; char x;
const sr dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 
sr v[M+1][M+1][3],n,m,rx,ry; bool node[M+1][M+1];
void dfs(sr x,sr y,sr x1,sr y1){if (v[x][y][2]&&(v[x][y][0]!=x1||v[x][y][1]!=y1)) {flag=1; return;}//找到自环if (v[x][y][2]&&v[x][y][0]==x1&&v[x][y][1]==y1) return;//没走到自环v[x][y][0]=x1; v[x][y][1]=y1; v[x][y][2]=1;for (sr k=0;k<4;k++){sr x2=x+dx[k],y2=y+dy[k]; if (x2<1) x2=n; if (x2>n) x2=1; if (y2<1) y2=m; if (y2>m) y2=1;if (node[x2][y2]) dfs(x2,y2,x1+dx[k],y1+dy[k]);}
}
int main(){ios::sync_with_stdio(0);while (cin>>n>>m){for (sr i=1;i<=n;i++)for (sr j=1;j<=m;j++){cin>>x; node[i][j]=0;v[i][j][0]=v[i][j][1]=v[i][j][2]=0;if (x=='#') continue;if (x=='S') rx=i,ry=j;node[i][j]=1;}flag=0; dfs(rx,ry,rx,ry); if (flag) cout<<"Yes"<<endl; else cout<<"No"<<endl;}return 0;
}

这篇关于#深搜#洛谷 1363 幻想迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---