#深搜#洛谷 1363 幻想迷宫

题目

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

---

分析

广搜，深搜
用v[x][y][0]$v[x][y][0]$表示横坐标，v[x][y][1]$v[x][y][1]$表示纵坐标。v[x][y][2]$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;
}