语文建设 官方网站,网络编辑是做什么的,室内装修公司哪家好,盐湖网站制作对于BFS的#xff0c;我来谈一谈自己的理解。首先#xff0c;我们从一道最基础的题来进行学习:
洛谷B3625 迷宫寻路#xff08;仔细阅读哦#xff0c;我就不解释了#xff09;
B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态
对于这道题以及所有的BFS题目的核心#x…对于BFS的我来谈一谈自己的理解。首先我们从一道最基础的题来进行学习:
洛谷B3625 迷宫寻路仔细阅读哦我就不解释了
B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态
对于这道题以及所有的BFS题目的核心我们的思想是这样的
直接暴力枚举每一种情况并把其放入队列因为队列符合BFS算法所需要的先进先出在枚举完这一种情况的所有符合条件的衍生情况并入队后把这一种情况出队枚举下一个也就是出队后的队首元素直至找到符合条件的答案。又或者是说枚举完了所有情况都没有找到正确答案在程序运行中体现这一点的是队列为空都没有找到答案的情况。
示例
有一个n*m的方格里面#的地方是不能走的起点是11)终点是nm那么如以下图形
.##.#
.#...
...#.
刚开始的队列数据类型可以是pair、结构体等
11 想要从11走到nm我们可以按刚才说的流程把11的所有衍生坐标入队而且入队条件为该区域不为#且在n*m以内。
入队后的队列
11 21
为什么只有21一个呢这是因为对于11来说不考虑入队条件11确实有四种衍生情况01211210但其中0110超出了n*m的范围而12则是不能通行的#区域所以最终只有21一个符合条件的坐标被加入到了队列。可到这就完了吗不我们在上面说过还需要把枚举完了所有情况的11节点出队因为它不是答案且没有了为答案提供价值的能力。这一点在代码里的体现不太一样在代码中作者是把11节点先用t保存起来再直接出队之后再用t代替11的作用。现在我们就完成了一次程序将要做的枚举。之后再照着这种方式继续即可求解出答案。 全部过程展示队列一行为一次枚举 11 21 31 32 33 23 24 25 26 因数据太水一条路拉通 代码实现 对于程序实现上的补充 进行一次枚举时我们需要一个标记来表示这个路段是否走过否则我们的程序会在两个路 段上反复横跳。 #includeiostream#includequeueusing namespace std;int n,m;bool tempfalse;char map[101][101];int vis[101][101]; int dx[5]{0,0,1,-1},dy[5]{1,-1,0,0};bool bfs(int map_x,int map_y){ if(map_xnmap_ym){ temptrue; } if(map_x1map_xnmap_y1map_ym){ for(int i0;i4;i){ int xxmap_xdx[i]; int yymap_ydy[i]; if(map[xx][yy]!#vis[xx][yy]!1){ vis[xx][yy]1; bfs(xx,yy); } } } return temp;}int main(){ cinnm; for(int i1;in;i){ for(int j1;jm;j){ cinmap[i][j]; } } bool xbfs(1,1); if(x){ coutYes; }else{ coutNo; } return 0;}
