递归求解迷宫中所有迷宫路径（数据结构学习笔记）

小咪咪 2022-12-28 04:21 125阅读 0赞

### 文章目录 ###

*  递归求解迷宫问题
 *   *  迷宫题目
     *  算法思路
     *  算法代码
     *   *  算法设计
         *  完整代码
     *  最终迷宫路径
     *  算法总结

--------------------

# 递归求解迷宫问题 #

有些问题可以使用递归方法求解，`将大问题分解成求解方法相同的小问题`。递归调用必须有的两个因素：**1、有递归出口，2、有递归体**。并且递归**调用的次数总是有限的**。

## 迷宫题目 ##

设计算法输出所有的迷宫路径，其中(1,1)为入口，(4,4)为出口。**（规定以0为可走方块，1为不可走方块）**

![在这里插入图片描述][20201214165121458.png]

int mg[M+2][N+2]=        //M=4，N=4 
        {
           {
        1, 1, 1, 1, 1, 1}, 
            {
        1, 0, 0, 0, 1, 1}, 
            {
        1, 0, 1, 0, 0, 1}, 
            {
        1, 0, 0, 0, 1 ,1}, 
            {
        1, 1, 0, 0, 0, 1}, 
            {
        1, 1, 1, 1, 1, 1}  };

## 算法思路 ##

采用递归算法求解迷宫问题，我们可以将由入口走向出口的大问题，分解为由(xs , ys)走到相邻可走方块(i , j)，再由(i , j)走向终点(xe , ye)的过程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

这里我们用path数组来存放迷宫路径

定义函数为

mgpath(int xi,int yi,int xe,int ye,PathType path)  //这里的PathType类型为自定义的path数组类型，后面做解释，这里看作path顺序表中存放每个方块的横纵坐标以及路径长度。

> 1、如果(xi,yi) == (xe,ye)
> 
>  *  将(xi , yi)存入path数组
>  *  输出Path数组中存放的迷宫路径
> 
> 2、如果(xi , yi) != (xe,ye)并且mg\[xi\]\[yi\]==0，对于(xi,yi)周围的每一个可走方块(i,j) `（这时，除了第一次是用到了起点(xs,ys)去调用迷宫函数，其他时刻都是每个方块周围的方块去调用迷宫函数）`
> 
>  *  将(xi,yi)存入path中
>  *  置mg\[xi\]\[yi\]=-1，避免来回走动
>  *  调用mgpath(i, j, xe, ye, path)，去递归考虑方块(i,j)周围的可走方块
>  *  path回退一步并且令mg\[i\]\[j\]=0

## 算法代码 ##

### 算法设计 ###

int count=0;	//记录当前为第几号迷宫路径 
    void mgpath(int xi,int yi,int xe,int ye,PathType path)
    {
        
    	int i,j;
    	
    	if(xi==xe&&yi==ye){
        
    		//将终点坐标进入路径中 
    		path.data[path.length].i=xi; 
    		path.data[path.length].j=yi;
    		path.length++;
    		
    		printf("迷宫路径 %d 如下：\n",++count);
    		for(int k=0;k<path.length;k++){
        
    			printf("\t(%d,%d)",path.data[k].i,path.data[k].j);
    			if((k+1)%5==0)		//每输出5个方块后换行 
    				printf("\n");
    		}
    		printf("\n");
    	}
    	else{
        
    		if(mg[xi][yi]==0){
        
    			int di=0;	//用于四个方位移动的变量
    			while(di<4){
        
    				//第一步：将(xi,yi)进入path路径中 
    				path.data[path.length].i=xi; 
    				path.data[path.length].j=yi;
    				path.length++;
    				
    				//对四个方位寻找相邻方块 
    				switch(di){
        
    					case 0:{
        i=xi-1,j=yi;break;}
    					case 1:{
        i=xi,j=yi+1;break;}
    					case 2:{
        i=xi+1,j=yi;break;}
    					case 3:{
        i=xi,j=yi-1;break;}
    				} 
    				
    				//第二步：将mg[xi][yi]=-1，避免来回走动 
    				mg[xi][yi]=-1;	
    				
    				//第三步：递归调用迷宫函数求解小问题 
    				mgpath(i,j,xe,ye,path);
    				
    				//第四步：回退path数组中的元素，并将回退元素mg[xi][yi]=0来寻找其他路径 
    				path.length--;
    				mg[xi][yi]=0;	
    				
    				di++;
    			} 
    		}
    	}	
    }

### 完整代码 ###

#include <stdio.h>
    #define M 4
    #define N 4
    
    int mg[M+2][N+2]=        //M=4，N=4 
        {
           {
        1, 1, 1, 1, 1, 1}, 
            {
        1, 0, 0, 0, 1, 1}, 
            {
        1, 0, 1, 0, 0, 1}, 
            {
        1, 0, 0, 0, 1 ,1}, 
            {
        1, 1, 0, 0, 0, 1}, 
            {
        1, 1, 1, 1, 1, 1}  };
    
    //方块类型定义 
    typedef struct
    {
        
    	int i;
    	int j;
    }Box;
    
    //路径类型定义 
    typedef struct
    {
        
    	Box data[10000];
    	int length;		//路径长度 
    }PathType; 
    
    int count=0;	//记录当前为第几号迷宫路径 
    void mgpath(int xi,int yi,int xe,int ye,PathType path)
    {
        
    	int i,j;
    	
    	if(xi==xe&&yi==ye){
        
    		//将终点坐标进入路径中 
    		path.data[path.length].i=xi; 
    		path.data[path.length].j=yi;
    		path.length++;
    		
    		printf("迷宫路径 %d 如下：\n",++count);
    		for(int k=0;k<path.length;k++){
        
    			printf("\t(%d,%d)",path.data[k].i,path.data[k].j);
    			if((k+1)%5==0)		//每输出5个方块后换行 
    				printf("\n");
    		}
    		printf("\n");
    	}
    	else{
        
    		if(mg[xi][yi]==0){
        
    			int di=0;	//用于四个方位移动的变量
    			while(di<4){
        
    				//第一步：将(xi,yi)进入path路径中 
    				path.data[path.length].i=xi; 
    				path.data[path.length].j=yi;
    				path.length++;
    				
    				//对四个方位寻找相邻方块 
    				switch(di){
        
    					case 0:{
        i=xi-1,j=yi;break;}
    					case 1:{
        i=xi,j=yi+1;break;}
    					case 2:{
        i=xi+1,j=yi;break;}
    					case 3:{
        i=xi,j=yi-1;break;}
    				} 
    				
    				//第二步：将mg[xi][yi]=-1，避免来回走动 
    				mg[xi][yi]=-1;	
    				
    				//第三步：递归调用迷宫函数求解小问题 
    				mgpath(i,j,xe,ye,path);
    				
    				//第四步：回退path数组中的元素，并将回退元素mg[xi][yi]=0来寻找其他路径 
    				path.length--;
    				mg[xi][yi]=0;	
    				
    				di++;
    			} 
    		}
    	}	
    } 
    
    int main()
    {
        
    	PathType path;
    	path.length=0;
    	mgpath(1,1,4,4,path);
    	
    	return 0;
    }

## 最终迷宫路径 ##

![3][]

## 算法总结 ##

用递归算法求解迷宫问题，可以更好的解决迷宫中所有路径解的问题，并且递归解法用巧妙的path数组回退来解决多路径解的问题，相比栈和队列解法更加精妙。并且因为已经求出了迷宫问题的全部路径，因此我们可以通过改进迷宫递归算法比较路径长度，与队列解法一样，得到最短迷宫路径解。**最重要的可以解决多条最短迷宫路径问题**

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[20201214165121458.png]: /images/20221120/2e5ac262906647aa94a57e14c86e175d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201214165126490.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[3]: https://img-blog.csdnimg.cn/20201214165134444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70