原题链接：1411 - 迷宫的路径-东方博宜OJ
题目描述
Mitch老鼠在森林里游玩，不小心走进了一个迷宫里面，这个迷宫是一个 n 行 m 列的矩阵，迷宫中有些格子是可以走的，有些格子是不能走的，能走的格子用 o （小写字母 o ）表示，不能走的格子用 # 表示。
Mitch选择走出迷宫的策略是：先向右，如果右边走不通则选择向下，如果下边走不通则选择向左，如果左边走不通则选择向上；如果四个方向都走不通，则后退选择其他能走的路径。
Mitch从类似下图所示的迷宫的左上角点进入迷宫（请注意：入口
和出口的
点都不是
# ），请问Mitch有哪些方法可以走出迷宫，走到(n,m) 点；请编程求出所有可能的路径，输出这些路径，如果不存在任何的路径可以走出迷宫，请输出 no。
输入
第一行包含两个整数 n 和 m ，中间用单个空格隔开，代表迷宫的行和列的数量。
接下来 n 行，每行 m 个字符，描述迷宫地图。字符只有o 或 # 两种，o 代表这个格子可以走，# 代表这个格子不能走。(4≤n,m≤10 )
输出
请按照Mitch选择的走出迷宫的策略，输出所有可能的路径，输出形式请参考样例输出的形式。
如果不存在任何的路径可以走出迷宫，请输出 no。
样例
输入
6 5 ooooo o#### ooooo #oo#o oooo# o#ooo
输出
1:1,1->2,1->3,1->3,2->3,3->4,3->5,3->5,4->6,4->6,5 2:1,1->2,1->3,1->3,2->3,3->4,3->5,3->6,3->6,4->6,5 3:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->5,4->6,4->6,5 4:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->6,3->6,4->6,5 5:1,1->2,1->3,1->3,2->4,2->4,3->5,3->5,4->6,4->6,5 6:1,1->2,1->3,1->3,2->4,2->4,3->5,3->6,3->6,4->6,5 7:1,1->2,1->3,1->3,2->4,2->5,2->5,3->5,4->6,4->6,5 8:1,1->2,1->3,1->3,2->4,2->5,2->5,3->6,3->6,4->6,5
来源
回溯 深搜 递归
标签
回溯 深搜 递归
题解
题目大意
一只叫 Mitch 的老鼠在森林里游玩时误入了一个迷宫，这个迷宫呈现为一个 n 行 m 列的矩阵形式。迷宫中的格子分为两种情况，能用小写字母 o 表示的格子是可以行走通过的，而用 # 表示的格子是不能走的 “障碍” 格子。Mitch 选择的走出迷宫策略是有特定顺序的，它会先尝试向右走，如果右边走不通就向下走，向下走不通就向左走，向左走不通就向上走，要是四个方向都走不通，那就后退去选择其他能走的路径。Mitch 从迷宫的左上角（入口，且入口点不是 # ）进入迷宫，需要编程求出它按照这个策略能走出迷宫到达右下角点 (n, m) 的所有可能路径，并按照规定格式输出这些路径，如果不存在任何可行的走出迷宫的路径，那就输出 no 。
代码思路
- 变量定义与初始化部分：
- 首先定义了一些必要的变量，比如
n和mn用来存储迷宫的行数和列数，t用于记录找到的可行路径数量（初始化为0），二维数组a[160][2]用于记录每条路径中经过的点的坐标，二维字符数组m[19][19]用来存储迷宫的布局情况。同时定义了表示四个方向偏移量的数组dx[]和dy[]，分别对应右、下、左、上四个方向在横坐标和纵坐标上的变化量（比如向右就是横坐标+1，纵坐标不变，对应dx[0]=0，dy[0]=1等）。
- 首先定义了一些必要的变量，比如
int n,mn,t=0,a[160][2];
char m[19][19];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
- 输出路径函数
p：- 这个函数的作用是按照规定格式输出一条找到的可行路径。它先输出路径的序号（也就是变量
t的值），然后通过循环遍历已经记录在数组a中的坐标点，按照x,y->的格式依次输出路径上经过的每个点，最后输出终点坐标(n, mn)。
- 这个函数的作用是按照规定格式输出一条找到的可行路径。它先输出路径的序号（也就是变量
void p(int c){// 输出路径序号printf("%d:",t);for(int i=1;i<=c;i++){// 输出路径上每个点的坐标格式printf("%d,%d->",a[i][0],a[i][1]);}// 输出终点坐标printf("%d,%d\n",n,mn);
}
- 深度优先搜索函数
dfs：- 递归终止条件判断：首先判断当前位置
(x, y)是否已经到达迷宫的右下角终点（即x == n且y == mn），如果到达了终点，说明找到了一条可行路径，此时将路径数量t加1，然后调用p函数输出这条路径（注意传入的参数是c - 1，因为数组a中记录路径的下标是从1开始的，这里要输出的是前面已经记录好的有效坐标个数），最后返回结束这次递归分支。
- 递归终止条件判断：首先判断当前位置
if(x==n&&y==mn){t++;//到达终点，增加一个路径p(c-1);return;
}
- 标记当前位置并记录坐标：将当前到达的位置
(x, y)在迷宫数组m中标记为#，表示已经走过了（避免重复走，起到类似剪枝的作用），然后把当前位置的坐标记录到数组a中，方便后续输出路径。
m[x][y]='#';//到达某点，标记
a[c][0]=x;
a[c][1]=y;
- 尝试四个方向探索：通过一个循环遍历四个方向（
i从0到3，分别对应右、下、左、上四个方向），先计算出按照当前方向走一步后的坐标h（横坐标）和l（纵坐标），接着判断这个新坐标是否在迷宫范围内（h > 0 && h <= n && l > 0 && l <= mn）并且对应格子是可以走的（m[h][l] == 'o'），如果满足这些条件，就以这个新坐标为起点进行递归调用dfs函数，继续探索下一步的路径，同时传入的路径记录长度参数c要加1，表示往下多走了一步，记录路径的位置往后移一位。
int h,l;
for(int i=0;i<4;i++){h=x+dx[i];l=y+dy[i];if(h>0&&h<=n&&l>0&&l<=mn&&m[h][l]=='o'){dfs(h,l,c+1);}
}
- 回溯操作：当从某个位置沿着四个方向探索完所有可能路径后（不管有没有找到可行路径），需要把当前位置的标记还原为
o，也就是撤销之前的标记，这样后续其他路径探索时这个位置还可以再次被访问到，这就是回溯的思想，保证了可以遍历所有可能的情况。
m[x][y]='o';//回溯
- 主函数部分：
- 首先从标准输入读取迷宫的行数
n和列数mn，然后通过两层循环逐行逐列地读取迷宫的布局情况（字符o或者#）并存入数组m中。接着以迷宫的左上角坐标(1, 1)作为起点，调用dfs函数开始深度优先搜索路径，初始的路径记录长度参数设为1。最后判断如果找到的路径数量t还是0，说明没有找到任何可行路径，那就输出no。
- 首先从标准输入读取迷宫的行数
int main(){cin>>n>>mn;for(int i=1;i<=n;i++){for(int j=1;j<=mn;j++){cin>>m[i][j];}}dfs(1,1,1);if(t==0)cout<<"no";return 0;
}
完整代码
#include<iostream>
#include<cstring>using namespace std;// 定义迷宫的行数、列数，路径数量，记录路径坐标的数组以及存储迷宫布局的数组
int n, mn, t = 0, a[160][2];
char m[19][19];// 定义四个方向在横坐标上的偏移量，顺序为右、下、左、上
int dx[] = { 0, 1, 0, -1 };
// 定义四个方向在纵坐标上的偏移量，顺序为右、下、左、上
int dy[] = { 1, 0, -1, 0 };// 函数功能：按照格式输出一条找到的可行路径
// 参数 c 表示当前已经记录在数组 a 中的路径坐标个数（不包含终点坐标）
void p(int c) {// 输出路径序号printf("%d:", t);for (int i = 1; i <= c; i++) {// 输出路径上每个点的坐标格式，用 -> 连接printf("%d,%d->", a[i][0], a[i][1]);}// 输出终点坐标printf("%d,%d\n", n, mn);
}// 深度优先搜索函数，用于探索迷宫路径
// 参数 x、y 表示当前所在位置的坐标，c 表示已经记录的路径坐标个数（包含当前位置坐标）
void dfs(int x, int y, int c) {// 判断是否到达终点（右下角坐标 (n, mn)）if (x == n && y == mn) {t++; // 到达终点，路径数量加 1p(c - 1); // 输出这条找到的路径，传入的参数是已经记录的有效坐标个数（不包含终点这次记录）return;}// 将当前位置标记为已走过（用 # 标记，避免重复走）m[x][y] = '#';// 记录当前位置坐标到数组 a 中，方便后续输出路径a[c][0] = x;a[c][1] = y;int h, l;// 循环尝试四个方向（右、下、左、上）for (int i = 0; i < 4; i++) {h = x + dx[i];l = y + dy[i];// 判断新坐标是否在迷宫范围内且对应格子可走（是 'o'）if (h > 0 && h <= n && l > 0 && l <= mn && m[h][l] == 'o') {// 满足条件则以新坐标为起点继续深度优先搜索，路径记录长度加 1dfs(h, l, c + 1);}}// 回溯操作，将当前位置标记还原为可走状态（'o'），方便其他路径探索时可以再次访问m[x][y] = 'o';
}int main() {cin >> n >> mn;// 读取迷宫的每一行每一列的布局情况（字符 'o' 或者 '#'）for (int i = 1; i <= n; i++) {for (int j = 1; i <= mn; j++) {cin >> m[i][j];}}// 从左上角坐标 (1, 1) 开始深度优先搜索路径，初始路径记录长度设为 1dfs(1, 1, 1);// 如果没有找到任何可行路径（路径数量 t 还是 0），输出 noif (t == 0)cout << "no";return 0;
}
本题考察的知识点
- 深度优先搜索（DFS）算法：本题核心就是运用深度优先搜索来遍历迷宫的所有可能路径，通过递归的方式不断深入探索每个位置的四个方向（按照特定顺序），直到找到终点或者所有可能路径都探索完为止。在探索过程中，需要合理地处理递归的终止条件（到达终点）、记录路径状态以及回溯操作，以保证能够完整且正确地遍历整个状态空间，找到所有符合要求的路径。
- 回溯思想：在代码中，当对某个位置沿着四个方向探索完后，需要把这个位置的标记还原（从
#变回o），这就是典型的回溯操作。回溯能够让算法在搜索过程中可以 “退回” 到之前的状态，去尝试其他可能的分支，避免遗漏某些可行的路径，是解决这类需要穷举所有可能情况问题的重要思想方法。 - 二维数组的应用：使用二维字符数组
m来存储迷宫的布局情况，通过对二维数组元素的访问、修改（标记已走过的位置等操作）来体现迷宫中各个格子的状态以及在搜索过程中的变化，考查了对二维数组基本操作和理解，包括如何根据坐标来定位和操作对应元素等知识点。 - 基本的输入输出操作：通过标准输入读取迷宫的行数、列数以及具体的布局字符，还有按照规定格式输出找到的路径或者提示没有路径的信息，考查了对
cin和cout等基本输入输出流的使用，以及按照特定格式进行字符串格式化输出（如printf函数按照指定格式输出路径坐标等）的能力。