网站建设年度计划,看房网,网站字体大小是多少合适,建设网站选择主机时费用最昂贵的方案是引言 之前刚学DFS的时候并不完全理解为什么递归可以一直往下做#xff0c;后来直到了递归的本质是栈#xff0c;就想着能不能手写栈来代替递归呢。当时刚学#xff0c;自己觉得水平不够就搁置了这个想法#xff0c;今天上数据结构老师正好讲了栈的应用#xff0c;其中就有… 引言 之前刚学DFS的时候并不完全理解为什么递归可以一直往下做后来直到了递归的本质是栈就想着能不能手写栈来代替递归呢。当时刚学自己觉得水平不够就搁置了这个想法今天上数据结构老师正好讲了栈的应用其中就有一个走迷宫问题于是写下这篇文章希望能帮助大家更好的理解DFS。 B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
DFS
#includebits/stdc.h
const int N110;
char g[N][N];
bool st[N][N];
int n,m;
int dx[]{0,1,0,-1};
int dy[]{1,0,-1,0};
int flag0;
void dfs(int x,int y)
{if(flag) return;if(xnym){flag1;return ;}for(int i0;i4;i){int axdx[i];int bydy[i];if(a1||b1||an||bm) 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::cinnm;for(int i1;in;i){for(int j1;jm;j){std::cing[i][j];}}st[1][1]true;dfs(1,1);if(!flag) std::coutNo\n;else std::coutYes\n;return 0;
} 因为这题数据是100所以DFS是过不了哒。正解应该是BFS。
栈 栈的写法可以直接ac效率可见一斑。
#includebits/stdc.h
const int N110;
typedef std::pairint,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 flag0;void dfs(int x,int y)
{std::stackPII stk;st[x][y]true;stk.push({x,y});while(!stk.empty()){auto tstk.top();int at.first;int bt.second;if(anbm){flag1;return ;}int ok0;for(int i0;i4;i){int naadx[i],nbbdy[i];if(g[na][nb]#) continue;if(st[na][nb]) continue;if(a1||b1||an||bm) continue;//这个点可以走ok1;st[na][nb]true; stk.push({na,nb});}if(!ok){//不回溯是因为到这一步说明这个点是死胡同 //st[stk.top().first][stk.top().second]0;stk.pop();}}return ;
}
signed main()
{std::cinnm;for(int i1;in;i){for(int j1;jm;j){std::cing[i][j];}}dfs(1,1);if(flag) std::coutYes\n;else std::coutNo\n;return 0;
}
BFS
宽度优先搜索
#includebits/stdc.h
typedef std::pairint,int PII;
const int N110;
int n,m;
char g[N][N];
int dist[N][N];
PII q[N*N];
int hh0,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(hhtt){PII tq[hh];for(int i0;i4;i){int at.firstdx[i];int bt.seconddy[i];if(dist[a][b]!-1) continue;if(g[a][b]#) continue;if(a1||b1||an||bm) continue;q[tt]{a,b};dist[a][b]dist[x][y]1;if(anbm) {std::coutYes;return ;}}}std::coutNo;return ;
}
signed main()
{std::cinnm;for(int i1;in;i){for(int j1;jm;j){std::cing[i][j];} }bfs(1,1);return 0;
}
