栈实现深度优先搜索

引言

之前刚学DFS的时候并不完全理解为什么递归可以一直往下做，后来直到了递归的本质是栈，就想着能不能手写栈来代替递归呢。当时刚学，自己觉得水平不够就搁置了这个想法，今天上数据结构老师正好讲了栈的应用，其中就有一个走迷宫问题，于是写下这篇文章，希望能帮助大家更好的理解DFS。

B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

DFS

#include<bits/stdc++.h>
const int N=110;
char g[N][N];
bool st[N][N];
int n,m;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int flag=0;
void dfs(int x,int y)
{if(flag) return;if(x==n&&y==m){flag=1;return ;}for(int i=0;i<4;i++){int a=x+dx[i];int b=y+dy[i];if(a<1||b<1||a>n||b>m) continue;if(g[a][b]=='#') continue;if(st[a][b]) continue;st[a][b]=true;dfs(a,b);if(flag) return;st[a][b]=false;}return ;
}
signed main()
{std::cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){std::cin>>g[i][j];}}st[1][1]=true;dfs(1,1);if(!flag) std::cout<<"No"<<'\n';else std::cout<<"Yes"<<'\n';return 0;
}

因为这题数据是100，所以DFS是过不了哒。正解应该是BFS。 

栈

 栈的写法可以直接ac，效率可见一斑。

#include<bits/stdc++.h>
const int N=110;
typedef std::pair<int,int> PII;
char g[N][N];
bool st[N][N];
int n,m;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int flag=0;void dfs(int x,int y)
{std::stack<PII> stk;st[x][y]=true;stk.push({x,y});while(!stk.empty()){auto t=stk.top();int a=t.first;int b=t.second;if(a==n&&b==m){flag=1;return ;}int ok=0;for(int i=0;i<4;i++){int na=a+dx[i],nb=b+dy[i];if(g[na][nb]=='#') continue;if(st[na][nb]) continue;if(a<1||b<1||a>n||b>m) continue;//这个点可以走ok=1;st[na][nb]=true; stk.push({na,nb});}if(!ok){//不回溯是因为到这一步说明这个点是死胡同 //st[stk.top().first][stk.top().second]=0;stk.pop();}}return ;
}
signed main()
{std::cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){std::cin>>g[i][j];}}dfs(1,1);if(flag) std::cout<<"Yes"<<'\n';else std::cout<<"No"<<'\n';return 0;
}

BFS

宽度优先搜索

#include<bits/stdc++.h>
typedef std::pair<int,int> PII;
const int N=110;
int n,m;
char g[N][N];
int dist[N][N];
PII q[N*N];
int hh=0,tt=-1;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};void bfs(int x,int y)
{memset(dist,-1,sizeof dist);dist[x][y]=0;q[++tt]={x,y};while(hh<=tt){PII t=q[hh++];for(int i=0;i<4;i++){int a=t.first+dx[i];int b=t.second+dy[i];if(dist[a][b]!=-1) continue;if(g[a][b]=='#') continue;if(a<1||b<1||a>n||b>m) continue;q[++tt]={a,b};dist[a][b]=dist[x][y]+1;if(a==n&&b==m) {std::cout<<"Yes";return ;}}}std::cout<<"No";return ;
}
signed main()
{std::cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){std::cin>>g[i][j];} }bfs(1,1);return 0;
}