逐日“亿“题 东方博宜OJ 1411 - 迷宫的路径
原题链接：1411 - 迷宫的路径-东方博宜OJ标题描述
Mitch老鼠在森林里嬉戏，不小心走进了一个迷宫内里，这个迷宫是一个 n 行 m 列的矩阵，迷宫中有些格子是可以走的，有些格子是不能走的，能走的格子用 o （小写字母 o ）表现，不能走的格子用 # 表现。
Mitch选择走出迷宫的计谋是：先向右，如果右边走不通则选择向下，如果下边走不通则选择向左，如果左边走不通则选择向上；如果四个方向都走不通，则后退选择其他能走的路径。
Mitch从类似下图所示的迷宫的左上角https://latex.csdn.net/eq?%281%2C1%29点进入迷宫（请注意：入口https://latex.csdn.net/eq?1%2C1 和出口的 https://latex.csdn.net/eq?n%2Cm点都不是 # ），叨教Mitch有哪些方法可以走出迷宫，走到(n,m) 点；请编程求出所有大概的路径，输出这些路径，如果不存在任何的路径可以走出迷宫，请输出 no。
https://i-blog.csdnimg.cn/img_convert/d46d676cb96cdeab0e504134bed8ab06.png
输入
第一行包含两个整数 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 用于记录每条路径中经过的点的坐标，二维字符数组 m 用来存储迷宫的布局环境。同时定义了表现四个方向偏移量的数组 dx[] 和 dy[]，分别对应右、下、左、上四个方向在横坐标和纵坐标上的变化量（比如向右就是横坐标 +1，纵坐标不变，对应 dx=0，dy=1 等）。
int n,mn,t=0,a;
char m;
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,a);
}
// 输出终点坐标
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='#';//到达某点，标记
a=x;
a=y;
[*]实验四个方向探索：通过一个循环遍历四个方向（i 从 0 到 3，分别对应右、下、左、上四个方向），先计算出按照当前方向走一步后的坐标 h（横坐标）和 l（纵坐标），接着判断这个新坐标是否在迷宫范围内（h > 0 && h <= n && l > 0 && l <= mn）而且对应格子是可以走的（m == 'o'），如果满足这些条件，就以这个新坐标为起点举行递归调用 dfs 函数，继承探索下一步的路径，同时传入的路径记录长度参数 c 要加 1，表现往下多走了一步，记录路径的位置今后移一位。
int h,l;
for(int i=0;i<4;i++){
h=x+dx;
l=y+dy;
if(h>0&&h<=n&&l>0&&l<=mn&&m=='o'){
dfs(h,l,c+1);
}
}
[*]回溯操作：当从某个位置沿着四个方向探索完所有大概路径后（不管有没有找到可行路径），需要把当前位置的标志还原为 o，也就是撤销之前的标志，这样后续其他路径探索时这个位置还可以再次被访问到，这就是回溯的头脑，保证了可以遍历所有大概的环境。
m='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;
}
}
dfs(1,1,1);
if(t==0)
cout<<"no";
return 0;
}
完整代码
#include<iostream>
#include<cstring>
using namespace std;
// 定义迷宫的行数、列数，路径数量，记录路径坐标的数组以及存储迷宫布局的数组
int n, mn, t = 0, a;
char m;
// 定义四个方向在横坐标上的偏移量，顺序为右、下、左、上
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, a);
}
// 输出终点坐标
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 = '#';
// 记录当前位置坐标到数组 a 中，方便后续输出路径
a = x;
a = y;
int h, l;
// 循环尝试四个方向（右、下、左、上）
for (int i = 0; i < 4; i++) {
h = x + dx;
l = y + dy;
// 判断新坐标是否在迷宫范围内且对应格子可走（是 'o'）
if (h > 0 && h <= n && l > 0 && l <= mn && m == 'o') {
// 满足条件则以新坐标为起点继续深度优先搜索，路径记录长度加 1
dfs(h, l, c + 1);
}
}
// 回溯操作，将当前位置标记还原为可走状态（'o'），方便其他路径探索时可以再次访问
m = 'o';
}
int main() {
cin >> n >> mn;
// 读取迷宫的每一行每一列的布局情况（字符 'o' 或者 '#'）
for (int i = 1; i <= n; i++) {
for (int j = 1; i <= mn; j++) {
cin >> m;
}
}
// 从左上角坐标 (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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]