广度优先遍历搜索迷宫最短路径

思路分析

由于广度是扩散逐层的方式遍历，相当于是多条路同时跑，最后先到终点就是最短路径了。

广度优先搜索主要使用队列来进行处理

路径用一个单独的vector存储，每一个点的坐标由二维转为一维，如(2, 3)存储在vector中下标为2*col + 3,这个位置存储到达(2, 3)的节点，即每个位置存储上个节点的位置。

测试用例

请输入迷宫的行列数(例如：10 10):6 6

请输入迷宫的路径信息(0表示可以走，1表示不能走):

0 0 1 1 1 1

1 0 0 0 0 1

1 0 1 1 0 1

1 0 0 0 0 1

1 0 1 1 1 1

1 0 0 0 0 0

结果为：

* * 1 1 1 1

1 * 0 0 0 1

1 * 1 1 0 1

1 * 0 0 0 1

1 * 1 1 1 1

1 * * * * *

如果用深度优先搜索则答案路径不是最短。为

* * 1 1 1 1

1 * * * * 1

1 0 1 1 * 1

1 * * * * 1

1 * 1 1 1 1

1 * * * * *

完整代码

#include <iostream>
#include <stack>
#include <queue>
using namespace std;// 用栈来模拟递归的dfs
// 定义迷宫每个节点的四个方向,从右开始，顺时针
const int RIGHT = 0;
const int DOWN = 1;
const int LEFT = 2;
const int UP = 3;// 迷宫每个节点方向的数量
const int WAY_NUM = 4;// 定义节点向某个方向行走是否可行
const int YES = 4;
const int NO = 5;class Maze
{
public:Maze(int row, int col): _row(row), _col(col){// 二维数组的创建_pMaze = new Node * [_row];for (int i = 0; i < _row; ++i){_pMaze[i] = new Node[_col];}// 将到达(i,j)的节点对象存入 _pPath[i * _row + j]_pPath.resize(_row * _col);}// 初始化迷宫每个节点对象void initNode(int x, int y, int val){_pMaze[x][y]._x = x;_pMaze[x][y]._y = y;_pMaze[x][y]._val = val;// 节点四个方向默认初始化for (int i = 0; i < WAY_NUM; ++i){_pMaze[x][y]._state[i] = NO;}}// 初始化迷宫0节点的四个方向的可达性void setNodeState(){for (int i = 0; i < _row; ++i){for (int j = 0; j < _row; ++j){//cout << "(" << _pMaze[i][j]._x << "," << _pMaze[i][j]._y << ") ";// (i,j) 本身就不可达if (_pMaze[i][j]._val == 1){continue;}//(i, j) 四个方向的可达性设置// 右侧可达性if (j < _col - 1 && _pMaze[i][j + 1]._val == 0){_pMaze[i][j]._state[RIGHT] = YES;}// 下方可达性if (i < _row - 1 && _pMaze[i + 1][j]._val == 0){_pMaze[i][j]._state[DOWN] = YES;}if (j > 0 && _pMaze[i][j - 1]._val == 0){_pMaze[i][j]._state[LEFT] = YES;}if (i > 0 && _pMaze[i - 1][j]._val == 0){_pMaze[i][j]._state[UP] = YES;}}cout << endl;}}// 深度搜索路径void searchMazePath(){if (_pMaze[0][0]._val == 1){return;}_queue.push(_pMaze[0][0]);while (!_queue.empty()){Node front = _queue.front();int x = front._x;int y = front._y;if (x == _row - 1 && y == _col - 1){return;}// 往右寻找if (_pMaze[x][y]._state[RIGHT] == YES){_pMaze[x][y]._state[RIGHT] = NO;// 防止再走回来_pMaze[x][y + 1]._state[LEFT] = NO;// 辅助数组中记录下一节点的行走路径信息_pPath[x * _row + y + 1] = _pMaze[x][y];_queue.push(_pMaze[x][y + 1]);if (check(_pMaze[x][y + 1])){return;}}// 往下寻找if (_pMaze[x][y]._state[DOWN] == YES){_pMaze[x][y]._state[DOWN] = NO;// 防止再走回来_pMaze[x + 1][y]._state[UP] = NO;_pPath[(x + 1) * _row + y] = _pMaze[x][y];_queue.push(_pMaze[x + 1][y]);if (check(_pMaze[x + 1][y])){return;}}// 往左寻找if (_pMaze[x][y]._state[LEFT] == YES){_pMaze[x][y]._state[LEFT] = NO;// 防止再走回来_pMaze[x][y - 1]._state[RIGHT] = NO;// 记录 到(x, y - 1) 的上一个节点_pPath[x * _row + y - 1] = _pMaze[x][y];				_queue.push(_pMaze[x][y - 1]);_queue.push(_pMaze[x][y - 1]);if (check(_pMaze[x][y - 1])){return;}}// 往上寻找if (_pMaze[x][y]._state[UP] == YES){_pMaze[x][y]._state[UP] = NO;// 防止再走回来_pMaze[x - 1][y]._state[DOWN] = NO;_pPath[(x - 1) * _row + y] = _pMaze[x][y];_queue.push(_pMaze[x - 1][y]);if (check(_pMaze[x - 1][y])){return;}}// 四个方向都无法走（可能是走过或者是值为1）_queue.pop();}}// 打印搜索结果void showMazePath(){if (_queue.empty()){cout << "不存在一条迷宫路径！" << endl;}else{// 因为_pPath存储每个节点的前一个节点// !!!从终点位置往前依次遍历找到路径int x = _row - 1;int y = _col - 1;for (;;){_pMaze[x][y]._val = '*';if (x == 0 && y == 0){break;}// 找前一个节点Node node = _pPath[x * _row + y];x = node._x;y = node._y;}for (int i = 0; i < _row; ++i){for (int j = 0; j < _col; ++j){if (_pMaze[i][j]._val == '*'){cout << "* ";}else{cout << _pMaze[i][j]._val << " ";}}cout << endl;}}}
private:// 定义迷宫每个节点的信息struct Node{int _x;int _y;int _val;int _state[WAY_NUM]; // 往四个方向走的可行性};// 检查是否到出口bool check(Node& node){return node._x == _row - 1 && node._y == _col - 1;}Node** _pMaze; // 二维数组存放迷宫int _row;int _col;queue<Node> _queue; // BFS依赖队列vector<Node> _pPath; // 记录BFS节点行走信息//stack<Node> _stack; // 用栈来代替递归进行深度搜索
};int main()
{cout << "请输入迷宫的行列数(例如：10 10):";int row, col, data;cin >> row >> col;Maze maze(row, col); // 创建迷宫对象cout << "输入迷宫的每个位置信息(0表示可以走，1表示不能走):" << endl;for (int i = 0; i < row; ++i){for (int j = 0; j < col; ++j){cin >> data;maze.initNode(i, j, data);}}// 开始设置所有节点四个方向的状态maze.setNodeState();// 从左上角开始搜索路径maze.searchMazePath();// 打印迷宫路径搜索结果maze.showMazePath();return 0;
}