548-深度优先遍历搜索迷宫路径

àì夳堔傛蜴生んèń 2022-09-11 04:11 163阅读 0赞

## 深度优先遍历搜索迷宫路径 ##

**深度遍历搜索迷宫路径，软件运行要求如下：**

请输入迷宫的行列数(例如：10 10):5 5
    请输入迷宫的路径信息(0表示可以走，1表示不能走):
    0 0 0 1 1
    1 0 1 0 1
    1 1 0 1 1
    1 1 0 0 1
    1 1 1 0 0
    
    迷宫路径搜索中...
    >>>如果没有路径(左上角的0到右下角的0没有一条通的路径)
    直接输出<<<
    不存在一条迷宫路径！
    
    迷宫路径搜索中...
    0 0 0 1 1
    1 0 0 0 1
    1 1 0 1 1
    1 1 0 0 1
    1 1 1 0 0
    >>>如果有路径，直接输出<<<
    * * * 1 1
    1 0 * 0 1
    1 1 * 1 1
    1 1 * * 1
    1 1 1 * *
    是路径的地方用*代替就可以了

**迷宫和节点的定义如下：**

//迷宫
    class Maze
    {
        	
    private:
    	//定义迷宫节点路径信息
    	struct Node
    	{
        
    		int _x;   
    		int _y;
    		int _val;//节点的值
    		int _state[WAY_NUM];//记录节点四个方向的状态(左右上下) 
    	};
    
    	Node **_pMaze;//动态生成迷宫路径(动态开辟二维数组) 
    	int _row;//迷宫的行 
    	int _col;//迷宫的列 
    	stack<Node> _stack;//栈结构，辅助深度搜索迷宫路径
    };

**如何深度搜索一个迷宫路径？**  
**非递归实现，需要一个栈**。  
深度优先遍历就是一个方向能走，就一直朝着这个方向(同一个方向)走。  
**我们给代码定义一下**：优先是向右边走，然后是向下走，然后是向左走，最后是向上走。  
迷宫的左上角元素坐标（0,0）的值是1的话，根本不存在迷宫通行的路径，入口就是封的了。  
如果是左上角元素坐标(0,0)的值是0的话，把它入栈。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
入栈以后，然后我们查看栈顶元素，是(0,0)这个节点，  
**我们的思路是这样：**  
栈现在不为空，取栈顶元素，先看它右边能不能走，能走的话，就一直向右走，它右边是0，就入栈了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]

再查看栈顶元素，看它的右边能不能走，假设它的右边和下面的元素值都是1，它左边是0，又走回到入口元素了，然后它的右边是0，就这样，不断来回走了。  
**所以，我们得这么判断：**  
如果栈顶元素的右边可以走的话，我们要把当前节点的右方向改成不能走，把右边节点的左方向改成不能走。**因为不能走回头路，而且因为路子走不通回退后也不能继续走相同的死路。**  
![在这里插入图片描述][7048bed4f06449e09d2d3ae2a5d6b4eb.png]  
因为是深度遍历，所以入栈后，不用判断之前节点的方向。  
continue后，重新取栈顶元素，继续进行判断。  
同理，如果右边不能走，下边可以走的话：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**同理：**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16 1]

**如果栈顶元素判断完四个方向都不能走，就是到死路了，就把栈顶元素出栈。**  
**然后再取栈顶元素，进行判断，如果它的4个方向都不能走，就出栈，如果栈为空，则迷宫无通路。如果有方向能走，就继续走下去。以此类推下去。**

**但是，都要判断一下此节点是不是右下角的节点，如果是，就是找到通路了。**  
![在这里插入图片描述][f269e91d96dd43b5ab6e89075453c84d.png]

## 代码实现 ##

#include <iostream>
    #include <stack>
    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];//注意元素类型是Node 
    		for (int i = 0; i < _row; ++i)
    		{
        
    			_pMaze[i] = new Node[_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节点四个方向的行走状态信息 当前节点右下左上，如果是0，改成可以走 
    	void setNodeState()
    	{
        
    		for (int i = 0; i < _row; ++i)
    		{
        
    			for (int j = 0; j < _col; ++j)
    			{
        
    				if (_pMaze[i][j]._val == 1)
    				{
        
    					continue;//不用调整了，因为走不到值为1的节点 
    				}
    				
                    //j不能取到最后一列，不然就判断越界了 
    				if (j < _col - 1 && _pMaze[i][j + 1]._val == 0)
    				//逻辑&，是先计算左边的表达式，左边如果是false，右边就不用计算了 
    				{
        
    					_pMaze[i][j]._state[RIGHT] = YES;
    				}
    
    				if (i < _row - 1 && _pMaze[i + 1][j]._val == 0)
    				{
        
    					_pMaze[i][j]._state[DOWN] = YES;
    				}
    				
                    //j不用取第一类，因为本身就不能走 
    				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;
    		}
    		_stack.push(_pMaze[0][0]);//左上角节点入栈 
    
    		while (!_stack.empty())//栈不为空 
    		{
        
    			Node top = _stack.top();
    			int x = top._x;
    			int y = top._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;
    				_stack.push(_pMaze[x][y + 1]);
    				continue;
    			}
    
    			//往下方向寻找
    			if (_pMaze[x][y]._state[DOWN] == YES)
    			{
        
    				_pMaze[x][y]._state[DOWN] = NO;
    				_pMaze[x + 1][y]._state[UP] = NO;
    				_stack.push(_pMaze[x + 1][y]);
    				continue;
    			}
    
    			//往左方向寻找
    			if (_pMaze[x][y]._state[LEFT] == YES)
    			{
        
    				_pMaze[x][y]._state[LEFT] = NO;
    				_pMaze[x][y - 1]._state[RIGHT] = NO;
    				_stack.push(_pMaze[x][y - 1]);
    				continue;
    			}
    
    			//往上方向寻找
    			if (_pMaze[x][y]._state[UP] == YES)
    			{
        
    				_pMaze[x][y]._state[UP] = NO;
    				_pMaze[x - 1][y]._state[DOWN] = NO;
    				_stack.push(_pMaze[x - 1][y]);
    				continue;
    			}
    
    			_stack.pop();
    		}
    	}
    
    	//打印迷宫路径搜索结果
    	void showMazePath()
    	{
        
    		if (_stack.empty())
    		{
        
    			cout << "不存在一条迷宫路径！" << endl;
    		}
    		else
    		{
        
    			while (!_stack.empty())//栈不为空，取出节点坐标，相应值调整为* 
    			{
        
    				Node top = _stack.top();
    				_pMaze[top._x][top._y]._val = '*';
    				_stack.pop();
    			}
    
    			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];//记录节点四个方向的状态(左右上下)
    		//4个元素位置(左右上下)，存储yes或者no 
    	};
    
    	Node **_pMaze;//动态生成迷宫路径(动态开辟二维数组) 
    	int _row;//迷宫的行 
    	int _col;//迷宫的列 
    	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)//只能获取i,j和data值，节点的4个方向的行走状态还不能初始化 
    	{
        
    		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 2]  
![在这里插入图片描述][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]: /images/20220828/20cfa7b74d52496b984132ca9bb5bdf1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f2df540c8d93413dbd4400f33ca1af8d.png
[7048bed4f06449e09d2d3ae2a5d6b4eb.png]: /images/20220828/9266eaae8c68400a80f6b3bca1eaea1a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0800d543289e40a9972b17a8b010594d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d25d95a093294a239f5485e3748f8bab.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ed5f61c91aec48dea94ccbabd31fdf78.png
[f269e91d96dd43b5ab6e89075453c84d.png]: /images/20220828/c0dfef51123f464994c3a9756bc1b2c0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/e6b55a1963c241da87443f02f05765b0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/115ca5caba9d47cdb9b65c22492b557c.png