深度优先搜索例题 |
您所在的位置：网站首页 › 深度优先搜索遍历例题 › 深度优先搜索例题 |
|
在阅读文章时，有文章说，深度优先算法常用来解决迷宫问题（迷宫问题不需要最优，只需要得到解即可）。 深搜在遍历一个树状图时，优先选择左节点，并沿着那个节点不断深入。但是在深入的时候，注意要记得标记这个节点已被遍历，因为随着深搜的进行必然会返回上一节点以达到其他的状态，然后再把这个节点放入栈中（不是队列哦！） 选择下一个节点时，是靠自己人为制定的规则来选择的，并不是必须选择左节点或右节点（广搜则必须是从左到右遍历），再将这个新的节点放入栈中（先看看是否有还没遍历一次的，遍历过一次的（已被标记）就不用再管。） 到了所有的路都被遍历过一次时，从栈里面弹出这个节点，看看栈里面深入一个节点是否有未被遍历到的节点……依次类推直到栈空。 这里推荐一篇博客！写的超级好！虽然也是转的，再前面的我就不知道谁是真正的作者啦~点击这里！ 深搜例题： （1） 题目链接：2815：城堡问题 第一次输入看不懂，题目看的差不多，看的出来是需要用深搜来做，后来去看了看别人的解析，才知道原来输入的是四个墙壁的综合，并且墙会被计算两次。 题目有递归和栈两种解法，emmm我尽量看懂了再发上来： 递归版做法： #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; int n, m; int room[55][55]； int color[55][55]; int color_num, max_room; int tmp_room; void dfs(int i, int j) { if(color[i][j]) // { return; } color[i][j] = color_num; tmp_room ++; if((room[i][j] & 1) == 0) dfs(i, j - 1);//巧妙运用位运算，来判断是否有墙，且这里位运算要加上括号，因为位运算优先级较低 （emmm这是什么基操，总之就是判断是否是墙的） if((room[i][j] & 2) == 0) dfs(i - 1, j); if((room[i][j] & 4) == 0) dfs(i, j + 1); if((room[i][j] & 8) == 0) dfs(i + 1, j); } int main() { while(scanf("%d %d", &n, &m) != EOF) { for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { scanf("%d", &room[i][j]); } } color_num = 0, max_room = 0; memset(color, 0, sizeof(color)); for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { tmp_room = 0;//判断每一个连通分量（即房间）里的大小 if(color[i][j] == 0) { color_num ++; dfs(i, j); max_room = max(max_room, tmp_room);//取最大值 } } } printf("%d\n%d\n", color_num, max_room);//房间数目和房间里面格子数目。 } return 0; } 栈形式的解法： #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; int n, m; int room[55][55]; int color[55][55]; int color_num, max_room; int tmp_room; struct Room { int i, j; Room(int _i, int _j) : i(_i), j(_j) //构造函数？ {} }; void dfs(int i, int j) { stack stk; stk.push(Room(i,j)); while(!stk.empty()) { Room rm = stk.top(); int p = rm.i, q |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |