接着上一篇的内容《全国大学生计算机技能应用（2020年）——C++科目决赛程序设计题解》最后一个题目：迷宫游戏。这一篇内容就来详解这道题目，并且复习由此延伸的内容：递归回溯算法。
0、问题来源
传送门：
《全国大学生计算机技能应用（2020年）——C++科目决赛程序设计题解》
1、迷宫问题简介
迷宫问题简介： 现有一个n * n的方格迷宫图，相当于二维数组，初始化中值为2表示█（墙壁），值为0表示可走空地。现在给定入口位置（starti，startj），出口位置（endi，endj）设计一种算法，算法中，当到达迷宫出口时，输出走出迷宫的通路；若未到达迷宫出口，并且存在可走路径即迷宫中为” “时，依次进行各个方向上的探索，直到找到将所有可能的结果试探完为止。如下图：
//给出的迷宫图，migo[1][0]为出发点，migo[7][8]为出口点
int migo[9][9]=
{
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{0, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 2, 2, 0, 2, 0, 2},
{2, 0, 2, 0, 0, 0, 2, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 2, 0, 0, 0, 0},
{2, 2, 2, 2, 2, 2, 2, 2, 2}
};
右上面进行图形化迷宫就像这样：
从图中我们很直观就看到走出迷宫的路径，以下坐标点为简化表示，可对应数组。出发点是（1,0）,出口点（7,8）。
既然这样，如何实现算法找到这一条路呢？
我们看看题目，发现要求是找出迷宫通路，没有其它约束或者额外的要求，目的明确，只要找到通路，对于不同迷宫图，存在的通路可能不止一条。如此甚好，我们将给定的出发点视为根结点，以此搜索子树，对每个子通道进行深度优先搜索，找到一个到达目的点通路时，回溯到根再次搜索问题解。
经过对问题解一番分析之后，不难发现，符合回溯法解题框架：递归回溯
2、回溯法
（1）基本思想
回溯法基本思想： 回溯法有“通用的解题法”之称，可以系统搜索一个问题的所有解或者任一解，既带有系统性又带有跳跃性的搜索算法。
- 在问题的姐空间树中，按深度优先策略，从根结点触发搜索解空间树，算法搜索至解空间树的任一结点时候，先判断该结点是否包含问题的解：
（1）如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其根结点回溯。
（2）包含问题的解，则进入子树，继续采用深度优先策略搜索。 - 回溯法求问题所有解时候，要回溯到根，且此时根结点的所有子树都已经被搜索过才结束。
- 回溯法求问题一个解时，只要搜索到问题的一个解就可以结束。
（2）子集树与排列树
刚刚提到的解空间树，常见的两类是子集树和排列数。
如何来区分呢？
划重点
a.当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树为子集树。
b.当所给问题是确定n个元素满足某种性质的排列时，其解空间为排列树。
//回溯法子集树一般算法
void backtrack(int t){
if(t>n)
output(n);
else{
for(int i=0;i<=1;i++){
x[t]=i;
if(constrain(t)&&bound(t))
backtrack(t+1);
}
}
}
//回溯法排列树一般算法
void backtrack(int t){
if(t>n)
output(n);
else{
for(int i=t;i<=n;i++){
swap(x[t],x[i]);
if(constrain(t)&&bound(t))
backtrack(t+1);
swap(x[t],x[i]);//搜索结束，回溯上一个状态
}
}
}
典型例子：
0-1背包问题解空间就是子集树，它是从n个物品中选择满足要求并且价值最大的子集。
旅行售货员问题解空间就是排列树，它是确定n个地点找到最佳路径的一个排列。
以上算法知识的了解和题目解析之后，回头看迷宫问题，它就是一个很好的可以使用回溯算法解决的问题，而且可知解空间树为子集树，根据上面的说法，换言之，我们要从n个可走的点找到一个子集，作为走出迷宫的通路！
3、迷宫解决
（1）递归出口
解题过程：
定义数组int way_value[9][9];来设置一个权值，用来判断迷宫的方向，指定1代表→，2代表↓，3代表← ，4代表向↑。
运用回溯子集树算法思想，我们的函数声明为void visit(int i,int j,int way)，( i , j )为当前所在位置，way的值表示前进方向。首先，问题解的输出，搜索迷宫路径相对应为：
/*
此为递归出口，如果一步步试探成功，即到达迷宫出口，则输出迷宫图"█"及路径"→↓←↑"
*/
if(i==endi&&j==endj)//判断有没有到到达迷宫出口，打印出所有走出迷宫的方法
{
cout<<endl;
for(int m=0; m<9; m++)
{
for(int n=0; n<9; n++)
{
if(migo[m][n]==2) //如果为值为2，表示迷宫中为"█"，不可走
cout<<"█";
else if(migo[m][n]==1)//可走方格
{
//输出路径方向，判断前进方向
//当前位置的way_value值 即1代表→，2代表↓，3代表← ，4代表向↑
if(way_value[m][n]==1)
cout<<"→";
if(way_value[m][n]==2)
cout<<"↓";
if(way_value[m][n]==3)
cout<<"←";
if(way_value[m][n]==4)
cout<<"↑";
}
else
cout<<" ";
}
cout<<endl;
}
}
（2）确定回溯方法
问题关键在于递归回溯的函数体部分，我们猜想，如果进入函数中，判断传值的点是否可走，并以此为根结点来搜索子树，那如何构造这个部分的函数？
我想到的方法是，既然要确定下一步走的方向，那就判断当前点的上下左右4个方向是否访问过并且可走，对可走的方向进一步搜索前进方向，否则，不对此结点进一步搜索。
//判断当前位置右边4个方向，如果未访问过，则标记way_values的值，递归
if(migo[i][j+1]==0)//判断右
visit(i,j+1,1);//对该点下一步搜索，way=1标记方向为右
if(migo[i+1][j]==0)//判断左，以此类推
visit(i+1,j,2);
if(migo[i][j-1]==0)
visit(i,j-1,3);
if(migo[i-1][j]==0)
visit(i-1,j,4);
此步骤可见得，只实现了递归，根据上面讲到的回溯思想和算法，搜索结束，要回溯根结点，需要回溯上一个状态，所以加上migo[i][j]=0;//恢复状态即可。
算法完整代码如下：
void visit(int i,int j,int way)
{
migo[i][j]=1; //当值为1表示此点可以走
way_value[i][j]=way;
/*
此为递归出口，如果一步步试探成功，即到达迷宫出口，则输出迷宫图"█"及路径"→↓←↑"
*/
if(i==endi&&j==endj)//判断有没有到到达迷宫出口，打印出所有走出迷宫的方法
{
cout<<endl;
for(int m=0; m<9; m++)
{
for(int n=0; n<9; n++)
{
if(migo[m][n]==2) //如果为值为2，表示迷宫中为"█"
cout<<"█";
else if(migo[m][n]==1)
{
//输出路径方向，判断前进方向
//当前位置的way_value值 即1代表→，2代表↓，3代表← ，4代表向↑
if(way_value[m][n]==1)
cout<<"→";
if(way_value[m][n]==2)
cout<<"↓";
if(way_value[m][n]==3)
cout<<"←";
if(way_value[m][n]==4)
cout<<"↑";
}
else
cout<<" ";
}
cout<<endl;
}
}
//判断当前位置右边4个方向，如果未访问过，则标记way_values的值，递归
if(migo[i][j+1]==0)//判断右
visit(i,j+1,1);//对该点下一步搜索，way=1标记方向为右
if(migo[i+1][j]==0)//判断左，以此类推
visit(i+1,j,2);
if(migo[i][j-1]==0)
visit(i,j-1,3);
if(migo[i-1][j]==0)
visit(i-1,j,4);
migo[i][j]=0;//恢复状态
}
4、迷宫游戏（完整代码）
迷宫问题完整程序：
#include<bits/stdc++.h>
using namespace std;
//初始化迷宫，点为2表示迷宫图为"█"，点为0表示迷宫图为" "
int migo[9][9]=
{
{2, 2, 2, 2, 2, 2, 2, 2, 2},
{0, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 2, 2, 0, 2, 0, 2},
{2, 0, 2, 0, 0, 0, 2, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 2, 0, 0, 0, 0},
{2, 2, 2, 2, 2, 2, 2, 2, 2}
};
//建立出迷宫图
int way_value[9][9];//设置一个权值，用来判断迷宫的方向
int starti=1,startj=0;//设置出发点为1,0
int endi=7,endj=8;//出口为7,7
/*
递归回溯算法：
算法中，当到达迷宫出口时，输出走出迷宫的通路；
若未到达迷宫出口，并且存在可走路径即迷宫中为" "时，依次进行
各个方向上的探索，直到找到将所有可能的结果试探完为止。
*/
void visit(int i,int j,int way)
{
migo[i][j]=1; //当值为1表示此点可以走
way_value[i][j]=way;
/*
此为递归出口，如果一步步试探成功，即到达迷宫出口，则输出迷宫图"█"及路径"→↓←↑"
*/
if(i==endi&&j==endj)//判断有没有到到达迷宫出口，打印出所有走出迷宫的方法
{
cout<<endl;
for(int m=0; m<9; m++)
{
for(int n=0; n<9; n++)
{
if(migo[m][n]==2) //如果为值为2，表示迷宫中为"█"
cout<<"█";
else if(migo[m][n]==1)
{
//输出路径方向，判断前进方向
//当前位置的way_value值 即1代表→，2代表↓，3代表← ，4代表向↑
if(way_value[m][n]==1)
cout<<"→";
if(way_value[m][n]==2)
cout<<"↓";
if(way_value[m][n]==3)
cout<<"←";
if(way_value[m][n]==4)
cout<<"↑";
}
else
cout<<" ";
}
cout<<endl;
}
}
//判断当前位置右边4个方向，如果未访问过，则标记way_values的值，递归
if(migo[i][j+1]==0)//判断右
visit(i,j+1,1);//对该点下一步搜索，way=1标记方向为右
if(migo[i+1][j]==0)//判断左，以此类推
visit(i+1,j,2);
if(migo[i][j-1]==0)
visit(i,j-1,3);
if(migo[i-1][j]==0)
visit(i-1,j,4);
migo[i][j]=0;//恢复状态
}
/********
main函数：
首先显示给出的迷宫图，然后调用visit函数，对迷宫进行探索
********/
int main()
{
int i,j;
cout<<"显示迷宫："<<endl;
for(i=0; i<9; i++)
{
for(j=0; j<9; j++)
if(migo[i][j]==2)
cout<<"█";
else
cout<<" ";
cout<<endl;
}
memset(way_value,0,sizeof(way_value));//初始化way_value数组全部为0
cout<<"迷宫路径如下：";
visit(starti,startj,1);
return 0;
}
对于该迷宫，输出路径如图：
后来我对迷宫图修改了一个值，验证程序的正确性，可走路径不止一条的情况下。输出了所有可走路径：
由此可知，递归回溯算法会搜索解空间树，找到所有可能的问题解。
以上是我对这个问题的解决思路和过程，学习记录并供大家参考，欢迎讨论交流指正！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/11371.html
