当你在夜晚孤军奋战时，满天星光以为你而闪烁。                                        

 

欢迎拜访：羑悻的小杀马特.-CSDN博客

本篇主题：轻轻松松拿捏洛谷走迷宫问题

制作日期：2024.12.31

隶属专栏：C/C++题海汇总

 

 

首先我们先进行对深搜及走迷宫进行一下了解之后在以例题深入：

 

目录

一·前言：

1.1深度优先搜索概述：

基本思想：

1.2走迷宫问题的应用场景：

 问题描述：

1.3DFS 解决走迷宫问题的实现步骤：

1.3.1数据结构准备：

1.3.2递归函数定义：

1.3.3搜索过程：

1.4优缺点：

 1.4.1优点：

1.4.2缺点：

1.5代码展示及其解释：

 二·走迷宫例题：

 三·分析操作：

细节处理：

 四·代码展示：

其他类似解法： 

五·本篇小结：

---

 

一·前言：

1.1深度优先搜索概述：

基本思想：

DFS 是一种用于遍历或搜索树或图的算法。它从根节点（对于图，可能是任意一个节点）开始，沿着一条路径尽可能深地访问节点，直到无法继续为止，然后回溯到上一个未完全探索的节点，继续搜索未访问的分支。

 

 

在搜索过程中，它使用栈（通常是递归调用栈）来存储待访问的节点信息，体现了后进先出（LIFO）的原则。

1.2走迷宫问题的应用场景：

 问题描述：

走迷宫问题通常可以抽象为一个二维矩阵，其中某些单元表示墙壁（不可通行），其他单元表示通道（可通行）。目标是从起点找到一条到达终点的路径。

 例如，一个mxn  的矩阵，用 0 表示通道，1 表示墙壁，需要找到从起点  (a，b)到终点(c，d ) 的可行路径。

1.3DFS 解决走迷宫问题的实现步骤：

1.3.1数据结构准备：

①迷宫表示：使用二维数组 maze[m][n] 存储迷宫的布局，0 或 1 表示通道或墙壁。

②标记数组：使用 visited[m][n] 标记节点是否已访问，避免重复访问。

③方向数组：使用 dx[] 和 dy[] 表示上下左右四个方向的偏移量，如 dx = {-1, 0, 1, 0}，dy = {0, 1, 0, -1}，表示上、右、下、左四个方向的坐标变化。

1.3.2递归函数定义：

①dfs(int x, int y) 是核心递归函数，其中 x 和 y 表示当前节点的坐标。

②函数首先检查当前节点是否为终点，如果是则表示找到路径；然后检查是否越界、是否是墙壁或已访问，如果都不是，则标记为已访问，并递归调用 dfs 函数对相邻节点进行搜索。

1.3.3搜索过程：

①从起点开始调用 dfs(start_x, start_y)。

②对于当前节点 (x, y)，依次尝试向四个方向移动（根据 dx 和 dy），并对满足条件（未越界、不是墙壁、未访问）的新节点调用 dfs 函数。

③如果某一方向的递归调用找到了路径，返回 true，否则回溯，将当前节点标记为未访问（即取消标记），尝试其他方向。

1.4优缺点：

 1.4.1优点：

简单直观：算法的实现相对简单，使用递归的方式易于理解和编写代码。

空间效率：使用递归调用栈存储节点信息，通常比使用显式的栈更简洁，空间复杂度在大多数情况下相对较低。

找到一条路径即可：如果只需要找到一条可行路径，DFS 可能会比广度优先搜索（BFS）更快，因为它会沿着一条路径一直探索下去，直到找到终点。

1.4.2缺点：

不一定是最短路径：由于其深度优先的特性，找到的路径可能不是最短路径，而是先找到的一条可行路径。

可能会陷入死胡同：如果迷宫中存在大量死胡同，DFS 可能会陷入较深的路径，导致时间复杂度较高，在最坏情况下可能会遍历整个搜索空间。

1.5代码展示及其解释：

#include <iostream>
#include <vector>

using namespace std;

// 定义方向偏移量，上、右、下、左
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 深度优先搜索函数
bool dfs(vector<vector<int>>& maze, vector<vector<bool>>& visited, int x, int y, int end_x, int end_y) {
    // 如果到达终点
    if (x == end_x && y == end_y) {
        return true;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        // 检查是否越界、不是墙壁、未访问
        if (new_x >= 0 && new_x < maze.size() && new_y >= 0 && new_y < maze[0].size() && maze[new_x][new_y] == 0 &&!visited[new_x][new_y]) {
            if (dfs(maze, visited, new_x, new_y, end_x, end_y)) {
                return true;
            }
        }
    }
    visited[x][y] = false; // 回溯，标记为未访问
    return false;
}

int main() {
    int m = 5, n = 5;
    vector<vector<int>> maze = {{0, 1, 0, 0, 0},
                            {0, 0, 0, 1, 0},
                            {0, 1, 0, 1, 0},
                            {0, 1, 0, 0, 0},
                            {0, 0, 0, 0, 0}};
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    int start_x = 0, start_y = 0;
    int end_x = 4, end_y = 4;
    if (dfs(maze, visited, start_x, start_y, end_x, end_y)) {
        cout << "Path found!" << endl;
    } else {
        cout << "No path found." << endl;
    }
    return 0;
}

 1·dfs 函数接收迷宫矩阵 maze、访问标记矩阵 visited 以及当前和终点的坐标。

2·首先检查是否到达终点，若到达则返回 true。

3·标记当前节点已访问，尝试四个方向的新节点，若新节点满足条件且递归调用 dfs 找到路径，则返回 true。

4·若都不满足，回溯并标记为未访问，返回 false。 

 

那么下面我们就以一道洛谷的实题来切入解法分析解法，以及细节处理和易错点：

 二·走迷宫例题：

测试用例： 

输入：

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

 输出：

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

 

洛谷原题链接：走迷宫 - 洛谷

 三·分析操作：

首先当我们看到是“网格”,肯定就想到了，暴搜法（当然了也可以和决策树联系起来，但是画出来就太繁琐了，在心里知道即可）；其次就是这个数据范围，也不是相对大：

因此，可以考虑走一下暴搜；即从起点对应的坐标开始去：

 

 

这里就是细节：左上右下的顺序。 

这里我们题目给的位置坐标和我们dfs中用的不是一样的（dfs是数组中的下标；但是放入path中就是实际我们所说的；因此不要忘记加减1的操作）

然后去搜索；找到不是墙即1就把对应的坐标按照规则添加进去；之后以它为中心去左上右下调用dfs；一直进行下去；直到找到了终点就把它放入ret（我们这里是采用数组记录，最后打印）

当然了其实还是有一些细节处理：

细节处理：

①比如我们的标记数组：

这里如果我们按照是1就进入；明显是不合适的；因为可能已经走过了；之后又回来：

因此这里我们建议搞一个全局的bool数组标记走过的痕迹；或者在原数组操作：每当走过就把此位置标记成0；等回溯回来的时候在进行复原即可（本篇介绍的是原数组操作）。 

② 其次，因为我们输出打印的是按照规则的所有路径；这里我们需要记录：

这里博主是搞了个path记录当前走的路线然后当找到终点就把它存入ret中（这样是全局的，就免不了手动的进行回溯删除等操作了）；当然了也可以搞成函数参数；然函数利用栈的性质自己解决（最后展示其他博主的写法）；这里我们就先以全局path为准：

为了不让dfs函数看起来乱，因此博主另外封装了函数：

void add(string &path, int x, int y) {//符合情况添加到path后面
    path += "(";
    path += to_string(x);
    path += ",";
    path += to_string(y);
    path  += ")";
    path += "->";
}

比如这个函数就为了添加当前坐标； 但是如果我们的坐标如果是类似13这样的两位数呢（题目要求最大是两位数）；因此转成string类型我们就要求一下长度，方便后序的删除操作了：

判断要删除多少个： 

int get_size(int x, int y) {//获得回溯时path要删除的字符长度
    return 5 + to_string(x).size() + to_string(y).size();
}//这里15to_stringsize是2；故这里要判断是一位数还是几位数

 回溯删除操作：

  int tmp2 = get_size(x+1,y+1);
  while (tmp2--)path.pop_back();

③有个我们很容易忽略的一点：

就是我们每次从起点进入dfs函数的时候需要把起点位置也标记上；后面防止重复走：

如果没有的话就直接35分啦：

 

因此这一步是不可或缺的： 

 v[sx-1][sy-1]=0;

还有就是无路径就cout -1；也就对应如果我们的ret数组size为0的操作。 

 ④左上右下搜索：

这里我们可以直接搞四个dfs函数，传递不同参数；但是这样就看起来太繁琐了；因此我们可以用向量法，搞一个数组存放中心坐标对应的偏移量：

/向量数组：完成左上右下搜索：
int xx[4] = { 0,-1,0,1 };
int yy[4] = { -1,0,1,0 };

这样的话，我们根据对中心坐标进行偏移一个循环，一个dfs就搞定了 ：

 for (int k = 0; k <= 3; k++) {//左上右下搜索
        int x = i + xx[k], y = j + yy[k];
        if (x >= 0 && x < m && y >= 0 && y < n && v[x][y] == 1) {
            v[x][y] = 0;//标记，防重
            add(path, x + 1, y + 1);
            dfs(v, x, y);
            //回溯：
            v[x][y] = 1;
            int tmp2 = get_size(x+1,y+1);
            while (tmp2--)path.pop_back();
        }

 四·代码展示：

#include<bits/stdc++.h>
using namespace std;
int m, n, sx, sy, tx, ty;//分别表示行数列数，起始坐标，终止坐标
//向量数组：完成左上右下搜索：
int xx[4] = { 0,-1,0,1 };
int yy[4] = { -1,0,1,0 };
string path;//记录每种答案
vector<string>ret;//答案数组
void add(string &path, int x, int y) {//符合情况添加到path后面
    path += "(";
    path += to_string(x);
    path += ",";
    path += to_string(y);
    path  += ")";
    path += "->";
}
int get_size(int x, int y) {//获得回溯时path要删除的字符长度
    return 5 + to_string(x).size() + to_string(y).size();
}//这里15to_stringsize是2；故这里要判断是一位数还是几位数
void dfs(vector<vector<int>>&v, int i, int j) {
    //递归出口；如果找到终止目标就放入ret，
    //但是此时如果进入这里path已经加入了终止坐标了
    if (i == tx - 1 && j == ty - 1) {
        //去除"->"
        path.pop_back();
        path.pop_back();
        ret.push_back(path);//放入ret
        path += "->";//复原，然后交给回溯操作完成删除
        return;
    }
    for (int k = 0; k <= 3; k++) {//左上右下搜索
        int x = i + xx[k], y = j + yy[k];
        if (x >= 0 && x < m && y >= 0 && y < n && v[x][y] == 1) {
            v[x][y] = 0;//标记，防重
            add(path, x + 1, y + 1);
            dfs(v, x, y);
            //回溯：
            v[x][y] = 1;
            int tmp2 = get_size(x+1,y+1);
            while (tmp2--)path.pop_back();
        }

    }

}
int main() {
    cin >> m >> n;
    vector<vector<int>>v(m, vector<int>(n));//不能全局：因为n,m未初始化
    //会崩;也可以是静态；但是注意大小范围即可
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }
    cin >> sx >> sy >> tx >> ty;
    add(path, sx, sy);
    v[sx-1][sy-1]=0;//细节：起始坐标必须标记，因为这个坐标不会在dfs中标记
    dfs(v, sx - 1, sy - 1);
    if (ret.size()) for (int i = 0; i < ret.size(); i++) cout << ret[i] << endl;
    else cout << "-1" << endl;//无路径就-1
  
    return 0;
}

最后也是通过：

 

其他类似解法： 

 上面我们不是说还可以把path搞成函数参数（利用函数特性完成自动回溯）以及不在原数组操作；搞了个bool数组来标记走过的路径：

那么它就来了：

#include<bits/stdc++.h>
using namespace std;
int a[17][17],s[17][17],n,m,bx,by,ex,ey;
const string c[16]={"0","1","2","3","4","5","6","7","8","9","10","11","12","13","14","15"};
//c用来将整数下标对应字符串的转换 
bool flag;//标记是否输出过解 
void dfs(int bx,int by,string ans){
    if(bx==ex&&by==ey){cout<<ans<<endl;flag=1;}//输出解并标记有路可走 
    int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};//四个方向搜索 
    for(int i=0;i<4;i++){
        int x=bx+d[i][0],y=by+d[i][1];        
        if(a[x][y]==1&&s[x][y]==0){
            s[x][y]=s[bx][by]+1;//深搜 
            dfs(x,y,ans+"->"+"("+c[x]+","+c[y]+")");//将经历过的点串联起来 
            s[x][y]=0;//回溯 
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];
    cin>>bx>>by>>ex>>ey;s[bx][by]=1;    
    dfs(bx,by,"("+c[bx]+","+c[by]+")");//起点(bx,by) 
    if(!flag)cout<<-1<<endl;    
    return 0;
}

当到当前坐标，以它为中心去查询；如果发现合适（为1）那么就让原先路径加上对应规则的坐标然后传给下一层；这样每次回溯回来就不用手动删除了（函数的形参变化不影响实参） ；其次就是搞了个s的标记数组；保证了原数组的完整性。

五·本篇小结：

 本篇用我们熟悉的dfs去暴搜（当然数据肯定不能太大）；其次就是我们设计dfs是如何的：

函数体（具体题目分析）；返回类型（一般根据是找所有情况（void）还是找一种即可（bool））；标记数组（防重复；如果原数组的值是特定的就可以对原数组操作，不需要外加全局bool数组），全局变量还是函数参数设计（像整型实型等这样变量就需要传参即可类似路径数组这样就得全局）；另外就是及时做好回溯和剪枝的处理。

 本篇分享结束了；欢迎大家多度支持呀！！！！