首页 > 代码库 > 走迷宫(同一)
走迷宫(同一)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=58
有关深搜广搜知识的讲解PPT链接:(一)http://wenku.baidu.com/link?url=uuVluDfJP-gW6FiV0F8J4s4VuEOU__uqW1nFjuOO-id9ntGdqXLLvwDN0eR3akZMKP_iBmA0xPGAE-SOwdWyN21HJoXrHbd7cvSx2zRkZBa
(二)http://wenku.baidu.com/view/67228040580216fc710afd1b.html?from=search
//走迷宫(一) //前提:迷宫图已知。给你一个起点和终点 //问题:至少几步到达终点 //问题隐含条件:1、肯定走得到终点;2,、求最短路径的问题(可以用队列+BFS) #include<iostream> using namespace std; #define min(a,b) a<b?a:b int Map[9][9] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int a, b, c, d, num; int dfs(int x, int y, int dep) //dep代表当前DFS的深度 { if (Map[x][y]) //if(走不下去了) { return 1; } if (x == c&&y == d) //if(找到解了) { num = min(dep, num); return 0; } //枚举下一种情况,DFS(...,dep+1) Map[x][y] = 1; dfs(x - 1, y, dep+1); dfs(x + 1, y, dep + 1); dfs(x, y - 1, dep + 1); dfs(x, y + 1, dep + 1); Map[x][y] = 0; } int main() { int n; cin >> n; while (n--) { num = 10000; cin >> a >> b>>c>>d; dfs(a,b,0); cout << num << endl; } }
相关链接:http://www.cnblogs.com/zhengbin/p/4495358.html
走迷宫(同一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。