首页 > 代码库 > 走迷宫(一)
走迷宫(一)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=58
有关深搜广搜知识的PPT讲解链接(1)http://wenku.baidu.com/link?url=uuVluDfJP-gW6FiV0F8J4s4VuEOU__uqW1nFjuOO-id9ntGdqXLLvwDN0eR3akZMKP_iBmA0xPGAE-SOwdWyN21HJoXrHbd7cvSx2zRkZBa
(2)http://wenku.baidu.com/view/67228040580216fc710afd1b.html?from=search
此题的方法:BFS+队列
//走迷宫(一) //前提:迷宫图已知。给你一个起点和终点 //问题:至少几步到达终点 //问题隐含条件:1、肯定走得到终点;2,、求最短路径的问题(可以用队列+BFS) #include<iostream> #include<stdio.h> #include<string> #include<algorithm> #include<queue> using namespace std; int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };//????? struct point { int x; int y; int step; }; int bfs(point s, point e, int map[9][9]) { queue<point>tp; int i; point u,t; s.step = 0; map[s.x][s.y] = 1; tp.push(s); //初始化队列Q while (!tp.empty()) //while(Q不为空) { u = tp.front(); //取出队首元素u; tp.pop(); if (u.x == e.x&&u.y == e.y) { return u.step; } for (int i = 0; i < 4; i++) //枚举队首元素u的相邻区域 { t.x = u.x + dir[i][0]; t.y = u.y + dir[i][1]; if (map[t.x][t.y] == 0) //if(此区域"有解") { t.step = u.step + 1; map[t.x][t.y] = 1; //访问标记 tp.push(t); //入队 } } } } int main() { int t; scanf("%d", &t); while (t--) { point s, e; 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 }; scanf("%d%d%d%d", &s.x, &s.y, &e.x, &e.y); printf("%d\n", bfs(s, e, map)); } return 0; }
走迷宫(一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。