摘要:本文主要向大家介绍了C++语言的实现DFS之“骨头的诱惑”,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
本文主要向大家介绍了C++语言的实现DFS之“骨头的诱惑”,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
深度优先搜索(DFS)是一个递归过程,有回退过程。
下面是一道OJ上的题目,借此来实现下DFS~
题目描述:
一只小狗在一个古老的迷宫里找到一根骨头,当它叼起骨头时,迷宫开始颤抖,它感觉到地
面开始下沉。它才明白骨头是一个陷阱,它拼命地试着逃出迷宫。
迷宫是一个N×M 大小的长方形,迷宫有一个门。刚开始门是关着的,并且这个门会在第T 秒
钟开启,门只会开启很短的时间(少于一秒),因此小狗必须恰好在第T 秒达到门的位置。每秒钟,
它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格,这个方格开始
下沉,而且会在下一秒消失。所以,它不能在一个方格中停留超过一秒,也不能回到经过的方格。
小狗能成功逃离吗?请你帮助他。
输入描述:
输入文件包括多个测试数据。每个测试数据的第一行为三个整数:N M T,(1<N, M<7;
0<T<50),分别代表迷宫的长和宽,以及迷宫的门会在第T 秒时刻开启。
接下来N 行信息给出了迷宫的格局,每行有M 个字符,这些字符可能为如下值之一:
X: 墙壁,小狗不能进入 S: 小狗所处的位置
D: 迷宫的门 . : 空的方格
输入数据以三个0 表示输入数据结束。
输出描述:
对每个测试数据,如果小狗能成功逃离,则输出"YES",否则输出"NO"。
样例输入:
3 4 5
S...
.X.X
...D
4 4 8
.X.X
..S.
....
DX.X
4 4 5
S.X.
..X.
..XD
....
0 0 0
样例输出:
YES
YES
NO
下面贴上代码+注释~
Code:
[cpp] view plain copy 1. #include<iostream> 2. #include<cmath> 3. using namespace std; 4. 5. char map[9][9]; //地图 6. int n, m, t; //迷宫的大小及门开启的时间 7. int dir[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; //4个方向 8. bool escape; //记录是否逃脱标志 9. 10. void dfs(int si, int sj, int di, int dj, int cnt) //cnt为所用时间 11. { 12. if(si>n || sj>m || si<=0 || sj<=0) return; //越界 13. if(si == di && sj == dj && cnt == t) //临界条件,在t时刻时走到出口~ 14. { 15. escape = 1; 16. return; 17. } 18. //剪枝(temp不能小于0且不能为奇数) 19. int temp = t-cnt - abs(si-di) - abs(sj-dj); 20. if(temp<0 || temp%2) return; 21. //DFS遍历 22. for(int i = 0; i < 4; i++) if(map[si+dir[i][0]][sj+dir[i][1]] != 'X') 23. { 24. map[si+dir[i][0]][sj+dir[i][1]] = 'X'; //将走过的地方设为墙壁 25. dfs(si+dir[i][0], sj+dir[i][1], di, dj, cnt+1); 26. if(escape) return; //当找到出口时,返回即可 27. map[si+dir[i][0]][sj+dir[i][1]] = '.'; //回退,恢复为可走点 28. } 29. return; 30. } 31. 32. int main() 33. { 34. int si, sj; //小狗所在位置 35. int di, dj; //出口所在位置 36. while(scanf("%d%d%d", &n, &m, &t)) //输入迷宫的长n、宽m、及出口处门开的时刻t 37. { 38. int wall = 0; //墙壁的数量,便于剪枝 39. getchar(); //屏蔽scanf后的转行符的影响 40. if(n == 0 && m == 0 && t == 0) break; //当输入"0 0 0"时结束 41. //确定小狗坐标、出口坐标、墙壁的数量 42. for(int i = 1; i <= n; i++) 43. { 44. for(int j = 1; j <= m; j++) 45. { 46. scanf("%c", &map[i][j]); 47. if(map[i][j] == 'S') { si = i; sj = j; } 48. else if(map[i][j] == 'D') { di = i; dj = j; } 49. else if(map[i][j] == 'X') wall++; 50. } 51. getchar(); //作用同上 52. } 53. 54. if(n*m <= t+wall) { printf("NO\n"); continue; } //剪枝 55. 56. escape = 0; 57. map[si][sj] = 'X'; 58. 59. dfs(si, sj, di, dj, 0); 60. 61. if(escape) printf("YES\n"); 62. else printf("NO\n"); 63. } 64. return 0; 65. }
运行结果:
Ps:如有bug,欢迎拍砖~
以上就介绍了C/C+的相关知识,希望对C/C+有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号