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

た入场券 2022-09-11 04:12 168阅读 0赞

## 寻找迷宫最短路径 ##

**在迷宫里面怎么找最短的路径？？？**  
![在这里插入图片描述][3a260bb8e19140ff9a4402f94ac82a27.png]

**使用广度遍历迷宫路径搜索最短路径：**

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

## 广度优先遍历求最短路径 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
如果(0,0)的值为1，则表示迷宫的路口是封住的，直接return掉。  
如果(0,0)的值为0，则表示路口是通的，把0入队。  
然后开启循环，如果队列不为空，看队头元素，它的右边能不能走，能走，则把右边元素入队，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

然后还要看(0,0)元素的下边，左边，上边能不能走，不能走，这个(0,0)元素看处理完了，出队。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

然后现在队头就是第一行的第二个元素了，然后先把它的左边，和(0,0）的右边修改为不能走，然后看这个元素右边能不能走，不能走，看下面能不能走，可以走，然后下面的元素就入队。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

然后队头元素还要看它的左边能不能走，不能走，上面能不能走，不能走，然后处理完了，就出队。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**此时的这个节点就是第二行第二个节点**  
然后看它右边能不能走，能走，右边元素入队。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

现在新元素是队列的队尾。队头即原来的元素还要继续判断，把所有的方向能走的元素都入队，现在看它的下面能不能走，可以走，下面的元素也入队，  
![在这里插入图片描述][93d7e3e0ea1f40ad9ddbd439de53dffc.png]  
然后看左边能不能走，不能走，上面能不能走，不能走，然后出队。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**现在的队头元素的第二行第三列的那个元素。队尾元素是第三行第二列的那个元素。**  
然后继续看队头元素，看它右边能不能走，能走，右边元素入队  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
它的下面，左边，上面都不能走。如果把这个队头元素出队。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

**现在的队头就是第三行的第二列元素，队尾元素就是第二行第四列的元素。**  
**以此类推下去。**  
**层层扩张**  
![在这里插入图片描述][7acf2743e8184496b60295599a2e31db.png]  
**在队列里，当把一个节点入队以后，我们发现这个队尾元素如果就是右下角的节点，就证明迷宫通路了，走到右下角的节点了。**  
队列里记录的是所有节点的行走状态，但是前面节点已经出队了，不在队列中。  
**这个队列存在的问题的：**  
![在这里插入图片描述][204cbf14bf944895bed319f6d32b78f9.png]

**队列只能找最短路径。但是最短路径的路径信息记录不下来。**  
![在这里插入图片描述][ad286187457a467b9439850fe998d3c8.png]  
**开辟多大的空间呢？我们只能使用最坏情况下的空间的大小去开辟。**  
**开辟 行乘以列 的大小的数组**  
![在这里插入图片描述][46b0a41739dc4e5486dd42cacd05d403.png]  
我们到达右下角的节点的时候，就是找到出口了，我们得在迷宫路径有哪些节点，我们要记录右下角的节点是从它左边这个节点过来的，怎么记录？  
**迷宫是二维数组，在内存上其实都是一维数组，所以我们把这个二维数组映射到下面这个一维数组当中。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**二维数组映射到一维数组的下标的公式如下：**  
![在这里插入图片描述][ffab63b4d9914acd973ce62f6d2b12db.png]  
**然后当前节点向哪个方向走，把这个信息记录一下，记在它要走到的那个节点对应的一维数组位置上，记录：当前节点是哪个节点来的。然后一直往前推，直到找到入口节点(0,0)，最短迷宫路径的路径信息就出来了。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]

## 代码实现 ##

#include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    
    //定义方向
    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];
    		}
    
    		//node._x*_row + node._y
    		_pPath.resize(_row * _col);//辅助数组开辟空间 
    	}
    
    	void initNode(int x, int y, int val)//初始化为No 
    	{
        
    		_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;
    		}
    	}
    
    	void setNodeState()//设置迷宫行走状态 
    	{
        
    		for (int i = 0; i < _row; ++i)
    		{
        
    			for (int j = 0; j < _col; ++j)
    			{
        
    				if (_pMaze[i][j]._val == 1)
    				{
        
    					continue;
    				}
    
    				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;
    				}
    			}
    		}
    	}
    
    	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 (_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;
    				_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[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;
    			}
    
    			//当前节点出队列
    			_queue.pop();
    		}
    	}
    
    	void showMazePath()//打印迷宫 
    	{
        
    		if (_queue.empty())
    		{
        
    			cout << "不存在一条迷宫路径！" << endl;
    		}
    		else
    		{
        
    			//回溯寻找迷宫路径节点
    			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;//广度遍历依赖的队列结构
    	vector<Node> _pPath;//记录广度优先遍历时，节点的行走信息，辅助数组 
    };
    
    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;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]

[3a260bb8e19140ff9a4402f94ac82a27.png]: /images/20220828/00f890b2b51f473e840a5c2d5705edc2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a97885b2d1524231921de5e6d6741326.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1d6575ae93d24bf8b5f7a2da714d69b2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/234bd572e29c42a4a0a6f9b4d78f1f3e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/881fedfd38a14b36b0cded9b26b1abd9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/4a5dea6e9cae4fd4a99cd68958cfd2ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/ebc6fc5cf47946db8835146fe6b2a786.png
[93d7e3e0ea1f40ad9ddbd439de53dffc.png]: /images/20220828/6b51cb92af0c40debb689bf45e7202df.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/d0dbb4cb7b394035a6157cb08fe3cc1b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/c331f77164844346ac1885ea810917a4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/3b5bca8108ba4e689724b7855d1944cd.png
[7acf2743e8184496b60295599a2e31db.png]: /images/20220828/691aaa73a8e54659aaacdef97c5b0b10.png
[204cbf14bf944895bed319f6d32b78f9.png]: /images/20220828/80268ad39d8043e188ed578e8bed97ff.png
[ad286187457a467b9439850fe998d3c8.png]: /images/20220828/826aa331f36842c58b6eee86b6475b18.png
[46b0a41739dc4e5486dd42cacd05d403.png]: /images/20220828/30ca26038fe34362899ad7c5fdb5c5c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/577df172a93144d79ff736a87576c09c.png
[ffab63b4d9914acd973ce62f6d2b12db.png]: /images/20220828/ab5d65b6851a4ef898ef7094c218f9fa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/bd5430e53ed74478894c48ea0a134740.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/dfd5e22151ea426e9d70081cb75e8312.png