原题链接：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，也就是撤销之前的标志，这样后续其他路径探索时这个位置还可以再次被访问到，这就是回溯的头脑，保证了可以遍历所有大概的环境。
- 主函数部分：
- 首先从标准输入读取迷宫的行数 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++; // 到达终点，路径数量加 1
- p(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') {
- // 满足条件则以新坐标为起点继续深度优先搜索，路径记录长度加 1
- dfs(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) 开始深度优先搜索路径，初始路径记录长度设为 1
- dfs(1, 1, 1);
- // 如果没有找到任何可行路径（路径数量 t 还是 0），输出 no
- if (t == 0)
- cout << "no";
- return 0;
- }
- 深度优先搜刮（DFS）算法：本题核心就是运用深度优先搜刮来遍历迷宫的所有大概路径，通过递归的方式不断深入探索每个位置的四个方向（按照特定序次），直到找到终点大概所有大概路径都探索完为止。在探索过程中，需要合理地处理递归的终止条件（到达终点）、记录路径状态以及回溯操作，以保证可以或许完整且精确地遍历整个状态空间，找到所有符合要求的路径。
- 回溯头脑：在代码中，当对某个位置沿着四个方向探索完后，需要把这个位置的标志还原（从 # 变回 o），这就是典型的回溯操作。回溯可以或许让算法在搜刮过程中可以 “退回” 到之前的状态，去实验其他大概的分支，制止遗漏某些可行的路径，是办理这类需要穷举所有大概环境问题的紧张头脑方法。
- 二维数组的应用：利用二维字符数组 m 来存储迷宫的布局环境，通过对二维数组元素的访问、修改（标志已走过的位置等操作）来体现迷宫中各个格子的状态以及在搜刮过程中的变化，考查了对二维数组根本操作和理解，包括如何根据坐标来定位和操尴尬刁难应元素等知识点。
- 根本的输入输出操作：通过标准输入读取迷宫的行数、列数以及详细的布局字符，还有按照规定格式输出找到的路径大概提示没有路径的信息，考查了对 cin 和 cout 等根本输入输出流的利用，以及按照特定格式举行字符串格式化输出（如 printf 函数按照指定格式输出路径坐标等）的本领。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
