首页 > 代码库 > 【每天一道算法题】走迷宫
【每天一道算法题】走迷宫
输入描述:
输入包含多组数据。
每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。
入口在第一行第二列；出口在最后一行第九列。
从任意一个“.”点都能一步走到上下左右四个方向的“.”点。
输出描述:
对应每组数据，输出从入口到出口最短需要几步。
输入例子:
#.########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
########.#
#.########
#........#
########.#
#........#
#.########
#........#
########.#
#........#
#.######.#
########.#
走迷宫，不应该说是一道题，应该说是一类题。之前华为OJ上也有。不过它只要求计算能不能走出迷宫，并没有要求最少步数。
其实就是构建一棵树。出口节点所在的层数就是其最少的步数，而start节点就是根节点。在这棵树上执行BFS算法。
自定义一个struct存储坐标位置，及该节点，所在层数。
BFS：
1、根节点入队列（这里是start入队）
2、读取其周围位置，类似其孩子节点。
3、判断是否到达出口节点，走到其孩子节点，将其标志为visited。
如果最后没有到达出口节点且队列已空，说明无法找到路径至出口，返回0。
#include <vector>#include <iostream>#include <queue>using namespace std; struct pos { int x; int y; int level;};int BFS(vector<vector<char>>& map) { const int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; queue<pos> q; int m = map.size(); int n = map[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); pos start = { 0,1,0 }, end = { 9,8,0 }; q.push(start); visited[start.x][start.y] = true; while (!q.empty()) { pos tmp = q.front(), nextpos; q.pop(); for (int i = 0; i < 4; i++) { nextpos.x = tmp.x + dir[i][0]; nextpos.y = tmp.y + dir[i][1]; nextpos.level = tmp.level + 1; if (nextpos.x == end.x&&nextpos.y == end.y) return nextpos.level; if (nextpos.x >= 0 && nextpos.x < m&&nextpos.y >= 0 && nextpos.y < n&&visited[nextpos.x][nextpos.y] == false&&map[nextpos.x][nextpos.y]==‘.‘) { q.push(nextpos); visited[nextpos.x][nextpos.y] = true; } } } return 0;} int main() { vector<vector<char>> map(10, vector<char>(10)); while (cin >> map[0][0]) { for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) { if (i == 0 && j == 0) continue; cin >> map[i][j]; } cout << BFS(map) << endl; } return 0;}
【每天一道算法题】走迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。