ToB企服应用市场:ToB评测及商务社交产业平台

标题: 逐日“亿“题 东方博宜OJ 1411 - 迷宫的路径 [打印本页]

---

作者: 天空闲话    时间: 2024-12-12 18:42
标题: 逐日“亿“题 东方博宜OJ 1411 - 迷宫的路径
原题链接：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。
样例
输入

1. 6 5
2. ooooo
3. o####
4. ooooo
5. #oo#o
6. oooo#
7. o#ooo

复制代码

输出

1. 1:1,1->2,1->3,1->3,2->3,3->4,3->5,3->5,4->6,4->6,5
2. 2:1,1->2,1->3,1->3,2->3,3->4,3->5,3->6,3->6,4->6,5
3. 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. 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. 5:1,1->2,1->3,1->3,2->4,2->4,3->5,3->5,4->6,4->6,5
6. 6:1,1->2,1->3,1->3,2->4,2->4,3->5,3->6,3->6,4->6,5
7. 7:1,1->2,1->3,1->3,2->4,2->5,2->5,3->5,4->6,4->6,5
8. 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 等）。
    
  
  

1. int n,mn,t=0,a[160][2];
2. char m[19][19];
3. int dx[]={0,1,0,-1};
4. int dy[]={1,0,-1,0};

复制代码

• 输出路径函数 p：
  
  
  
  • 这个函数的作用是按照规定格式输出一条找到的可行路径。它先输出路径的序号（也就是变量 t 的值），然后通过循环遍历已经记录在数组 a 中的坐标点，按照 x,y-> 的格式依次输出路径上经过的每个点，末了输出终点坐标 (n, mn) 。
    
  
  

1. void p(int c){
2.     // 输出路径序号
3.     printf("%d:",t);
4.     for(int i=1;i<=c;i++){
5.         // 输出路径上每个点的坐标格式
6.         printf("%d,%d->",a[i][0],a[i][1]);
7.     }
8.     // 输出终点坐标
9.     printf("%d,%d\n",n,mn);
10. }

复制代码

• 深度优先搜刮函数 dfs：
  
  
  
  • 递归终止条件判断：首先判断当前位置 (x, y) 是否已经到达迷宫的右下角终点（即 x == n 且 y == mn），如果到达了终点，说明找到了一条可行路径，此时将路径数目 t 加 1，然后调用 p 函数输出这条路径（注意传入的参数是 c - 1，因为数组 a 中记录路径的下标是从 1 开始的，这里要输出的是前面已经记录好的有用坐标个数），末了返回竣事这次递归分支。
    
  
  

1. if(x==n&&y==mn){
2.     t++;//到达终点，增加一个路径
3.     p(c-1);
4.     return;
5. }

复制代码

• 标志当前位置并记录坐标：将当前到达的位置 (x, y) 在迷宫数组 m 中标志为 #，表现已经走过了（制止重复走，起到类似剪枝的作用），然后把当前位置的坐标志录到数组 a 中，方便后续输出路径。
  

1. m[x][y]='#';//到达某点，标记
2. a[c][0]=x;
3. a[c][1]=y;

复制代码

• 实验四个方向探索：通过一个循环遍历四个方向（i 从 0 到 3，分别对应右、下、左、上四个方向），先计算出按照当前方向走一步后的坐标 h（横坐标）和 l（纵坐标），接着判断这个新坐标是否在迷宫范围内（h > 0 && h <= n && l > 0 && l <= mn）而且对应格子是可以走的（m[h][l] == 'o'），如果满足这些条件，就以这个新坐标为起点举行递归调用 dfs 函数，继承探索下一步的路径，同时传入的路径记录长度参数 c 要加 1，表现往下多走了一步，记录路径的位置今后移一位。
  

1. int h,l;
2. for(int i=0;i<4;i++){
3.     h=x+dx[i];
4.     l=y+dy[i];
5.     if(h>0&&h<=n&&l>0&&l<=mn&&m[h][l]=='o'){
6.         dfs(h,l,c+1);
7.     }
8. }

复制代码

• 回溯操作：当从某个位置沿着四个方向探索完所有大概路径后（不管有没有找到可行路径），需要把当前位置的标志还原为 o，也就是撤销之前的标志，这样后续其他路径探索时这个位置还可以再次被访问到，这就是回溯的头脑，保证了可以遍历所有大概的环境。
  

1. m[x][y]='o';//回溯

复制代码

• 主函数部分：
  
  
  
  • 首先从标准输入读取迷宫的行数 n 和列数 mn，然后通过两层循环逐行逐列地读取迷宫的布局环境（字符 o 大概 #）并存入数组 m 中。接着以迷宫的左上角坐标 (1, 1) 作为起点，调用 dfs 函数开始深度优先搜刮路径，初始的路径记录长度参数设为 1。末了判断如果找到的路径数目 t 还是 0，说明没有找到任何可行路径，那就输出 no 。
    
  
  

1. int main(){
2.     cin>>n>>mn;
3.     for(int i=1;i<=n;i++){
4.         for(int j=1;j<=mn;j++){
5.             cin>>m[i][j];
6.         }
7.     }
8.     dfs(1,1,1);
9.     if(t==0)
10.         cout<<"no";
11.     return 0;
12. }

复制代码

完整代码

1. #include<iostream>
2. #include<cstring>
4. using namespace std;
6. // 定义迷宫的行数、列数，路径数量，记录路径坐标的数组以及存储迷宫布局的数组
7. int n, mn, t = 0, a[160][2];
8. char m[19][19];
10. // 定义四个方向在横坐标上的偏移量，顺序为右、下、左、上
11. int dx[] = { 0, 1, 0, -1 };
12. // 定义四个方向在纵坐标上的偏移量，顺序为右、下、左、上
13. int dy[] = { 1, 0, -1, 0 };
15. // 函数功能：按照格式输出一条找到的可行路径
16. // 参数 c 表示当前已经记录在数组 a 中的路径坐标个数（不包含终点坐标）
17. void p(int c) {
18.     // 输出路径序号
19.     printf("%d:", t);
20.     for (int i = 1; i <= c; i++) {
21.         // 输出路径上每个点的坐标格式，用 -> 连接
22.         printf("%d,%d->", a[i][0], a[i][1]);
23.     }
24.     // 输出终点坐标
25.     printf("%d,%d\n", n, mn);
26. }
28. // 深度优先搜索函数，用于探索迷宫路径
29. // 参数 x、y 表示当前所在位置的坐标，c 表示已经记录的路径坐标个数（包含当前位置坐标）
30. void dfs(int x, int y, int c) {
31.     // 判断是否到达终点（右下角坐标 (n, mn)）
32.     if (x == n && y == mn) {
33.         t++;  // 到达终点，路径数量加 1
34.         p(c - 1);  // 输出这条找到的路径，传入的参数是已经记录的有效坐标个数（不包含终点这次记录）
35.         return;
36.     }
37.     // 将当前位置标记为已走过（用 # 标记，避免重复走）
38.     m[x][y] = '#';
39.     // 记录当前位置坐标到数组 a 中，方便后续输出路径
40.     a[c][0] = x;
41.     a[c][1] = y;
42.     int h, l;
43.     // 循环尝试四个方向（右、下、左、上）
44.     for (int i = 0; i < 4; i++) {
45.         h = x + dx[i];
46.         l = y + dy[i];
47.         // 判断新坐标是否在迷宫范围内且对应格子可走（是 'o'）
48.         if (h > 0 && h <= n && l > 0 && l <= mn && m[h][l] == 'o') {
49.             // 满足条件则以新坐标为起点继续深度优先搜索，路径记录长度加 1
50.             dfs(h, l, c + 1);
51.         }
52.     }
53.     // 回溯操作，将当前位置标记还原为可走状态（'o'），方便其他路径探索时可以再次访问
54.     m[x][y] = 'o';
55. }
57. int main() {
58.     cin >> n >> mn;
59.     // 读取迷宫的每一行每一列的布局情况（字符 'o' 或者 '#'）
60.     for (int i = 1; i <= n; i++) {
61.         for (int j = 1; i <= mn; j++) {
62.             cin >> m[i][j];
63.         }
64.     }
65.     // 从左上角坐标 (1, 1) 开始深度优先搜索路径，初始路径记录长度设为 1
66.     dfs(1, 1, 1);
67.     // 如果没有找到任何可行路径（路径数量 t 还是 0），输出 no
68.     if (t == 0)
69.         cout << "no";
70.     return 0;
71. }

复制代码

本题考察的知识点

• 深度优先搜刮（DFS）算法：本题核心就是运用深度优先搜刮来遍历迷宫的所有大概路径，通过递归的方式不断深入探索每个位置的四个方向（按照特定序次），直到找到终点大概所有大概路径都探索完为止。在探索过程中，需要合理地处理递归的终止条件（到达终点）、记录路径状态以及回溯操作，以保证可以或许完整且精确地遍历整个状态空间，找到所有符合要求的路径。
  
• 回溯头脑：在代码中，当对某个位置沿着四个方向探索完后，需要把这个位置的标志还原（从 # 变回 o），这就是典型的回溯操作。回溯可以或许让算法在搜刮过程中可以 “退回” 到之前的状态，去实验其他大概的分支，制止遗漏某些可行的路径，是办理这类需要穷举所有大概环境问题的紧张头脑方法。
  
• 二维数组的应用：利用二维字符数组 m 来存储迷宫的布局环境，通过对二维数组元素的访问、修改（标志已走过的位置等操作）来体现迷宫中各个格子的状态以及在搜刮过程中的变化，考查了对二维数组根本操作和理解，包括如何根据坐标来定位和操尴尬刁难应元素等知识点。
  
• 根本的输入输出操作：通过标准输入读取迷宫的行数、列数以及详细的布局字符，还有按照规定格式输出找到的路径大概提示没有路径的信息，考查了对 cin 和 cout 等根本输入输出流的利用，以及按照特定格式举行字符串格式化输出（如 printf 函数按照指定格式输出路径坐标等）的本领。 
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4