目录

问题描述

利用DFS（深度优先搜索）求解

利用BFS（广度优先搜索）求解

---

问题描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编写程序找出从左上角到右下角的路线。入口点为[0,0]，既第一格是可以走的路。

数据范围： 2≤n,m≤10 ， 输入的内容只包含 0≤val≤1 

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例1

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

 示例2

输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

输出：

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

说明：注意：不能斜着走！！

这个是一个搜索求最短路径的问题，下面我将分别讲解用 dfs（深度优先搜索）和 bfs（广度优先搜索）两种方法求解的过程。

利用DFS（深度优先搜索）求解

深度优先搜索就是一条路走到底，遇见目标点或走到死胡同才回溯。针对本题DFS如下：

首先，将图输入进来。用map二维数组存储这个简单图（0表示可以走，1表示障碍物），n、m表示图大小，end_x、end_y表示终点坐标。

cin >> n >> m;
end_x=n-1,end_y=m-1; //终点
for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
        cin>>map[i][j];

如果起点就是障碍物，那就废了，说明输入错误，直接退出。

if(map[0][0]==1){
    cout<<"No path exist."<<endl;
    return 0;
}

接着把起点标记为已访问，并加入路径，就可以开始 depth 了。其中，v[ ][ ] 用来存储点的访问信息（0表示该点未访问，1表示已访问），path 是一个 pair 类型的结构体数组，用于表示当前路径（走过的点）。

有小伙伴可能不知道 pair 是个啥，简单来说 pair 是一个结构体，主要由两个成员变量 first、second 组成，它俩的类型可以相同也可以不同。这个 pair 结构体可以很好地用在这道题表示坐标。其他更多用法可以查看C++ pair的基本用法总结（整理）_c++ pair用法-CSDN博客

v[0][0]=1;  //起点标记为已访问
path.push_back(make_pair(0,0));  //加入路径
dfs(0,0,0);  //从起点开depth

dfs 是一个递归函数，其传入的三个参数分别是当前点的x、y坐标和当前路径长度。

void dfs(int x,int y,int step)

在 dfs 函数中，我们首先检查是否到达终点（end_x，end_y）了，如果到达了，那么当前的路径长度是否比之前搜索到的最短路径短，如果是的话就把当前路径 path 更新到最短路径记录 shortesPath 中，然后直接返回。

if(x==end_x&&y==end_y){   //如果到终点了
    if(step<step_min){   //如果本次路径更短
        step_min=step;
        shortestPath=path;  //记录最短路径
    }
    return;
}

如果没到达，就接着往下走，往当前点的上下左右点走。在此题中，我规定它先向右走，再往下走，再往左走，再往上走。这个 for 循环就实现了上下左右的遍历。

当前位置是（x，y），如果往右走就是（x，y+1），往下走就是（x+1，y），往左走就是（x，y-1），往下走就是（x-1，y）。所以为了简洁方便，定义一个移动增量数组

const int dx[4]={0,1,0,-1};  //上下左右的移动增量
const int dy[4]={1,0,-1,0};

在 for 循环中，用 tx=x+dx[ i ]，ty=y+dy[ i ] 获得四个方向的坐标。

如果这个坐标满足条件：在迷宫范围内 && 未被访问 && 不是障碍物 ，就允许访问它，把它标记为已访问，加入路径，然后再 dfs 。

等到该点周围的点都被访问过后，会把该点取消 visited 标记，移出当前路径，然后回溯。

    for(int i=0;i<4;++i){  //遍历上下左右
        int tx=x+dx[i],ty=y+dy[i];
        if(v[tx][ty]==0&&map[tx][ty]==0&&
                tx>=0&&tx<=end_x&&ty>=0&&ty<=end_y){  //检查tx，ty符不符合条件 
            path.push_back(make_pair(tx,ty));  //将当前访问点加入路径
            v[tx][ty]=1;  //标记该点已访问
            dfs(tx,ty,step+1);
            v[tx][ty]=0;   //回溯取消标记
            path.pop_back();
        }
    }

从起点出发，回到起点结束。当起点周围的点都被访问过时，dfs 过程便结束了。返回主函数打印最短路径。前面已经说过，我们本题分别用 pair 结构体里的 first 、second 表示 x 、y 坐标。

for(int i=0;i<=step_min;i++)  //输出最短路径
    cout<<"("<<shortestPath[i].first<<","<<shortestPath[i].second<<")"<<endl;

完整代码：

#include <iostream>
#include <vector>
using namespace std;
int n, m; //迷宫矩阵大小
int map[11][11]={0};  //0表示可以走，1表示障碍物
int v[11][11]={0}; //0表示该点未访问，1表示已访问
int end_x,end_y;  //终点坐标
int step_min=999;  //最短路径长度
vector<pair<int,int> > path;  //当前路径
vector<pair<int,int> > shortestPath;  //最短路径记录
const int dx[4]={0,1,0,-1};  //上下左右的移动增量
const int dy[4]={1,0,-1,0};

void dfs(int x,int y,int step){    
    if(x==end_x&&y==end_y){   //如果到终点了
        if(step<step_min){   //如果本次路径更短
            step_min=step;
            shortestPath=path;  //记录最短路径
        }
        return;
    }
    if(step>=step_min)  //避免进行不必要的递归
        return;
    for(int i=0;i<4;++i){  //遍历上下左右
        int tx=x+dx[i],ty=y+dy[i];
        if(v[tx][ty]==0&&map[tx][ty]==0&&
                tx>=0&&tx<=end_x&&ty>=0&&ty<=end_y){  //检查tx，ty符不符合条件 
            path.push_back(make_pair(tx,ty));  //将当前访问点加入路径
            v[tx][ty]=1;  //标记该点已访问
            dfs(tx,ty,step+1);
            v[tx][ty]=0;   //回溯取消标记
            path.pop_back();
        }
    }
}

int main() {
    cin >> n >> m;
    end_x=n-1,end_y=m-1; //终点
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cin>>map[i][j];
    
    if(map[0][0]==1){
        cout<<"No path exist."<<endl;
        return 0;
    }

    v[0][0]=1;  //起点已访问
    path.push_back(make_pair(0,0));
    dfs(0,0,0);  //从起点开depth

    if (shortestPath.empty()) 
        cout << "No path exist." << endl;
    else
        for(int i=0;i<=step_min;i++)  //输出最短路径
            cout<<"("<<shortestPath[i].first<<","<<shortestPath[i].second<<")"<<endl;

    return 0;
}

利用BFS（广度优先搜索）求解

广度优先就是覆盖式、地毯式搜索，一旦找到目标，便得到最短路径。在本题中，如果迷宫很大，DFS很可能走很多冤枉路，BFS要优于DFS。

首先，将图输入进来。用map二维数组存储这个简单图（0表示可以走，1表示障碍物），n、m表示图大小，end_x、end_y表示终点坐标。

cin >> n >> m;
end_x=n-1,end_y=m-1; //终点
for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
        cin>>map[i][j];

如果起点就是障碍物，说明输入错误，直接退出。

if(map[0][0]==1){
    cout<<"No path exist."<<endl;
    return 0;
}

调用 bfs ，什么参数也没有。

void bfs()

在进入函数之前，先定义一个 Node 结构体，用于存储每一个节点的状态，包括：

• x 和 y：当前节点的坐标。
• step：从起点到当前节点的步数。
• path：当前路径经过的所有坐标，用 vector 存储 pair<int, int>。

struct Node {
    int x, y, step;  //当前点坐标，到起点步数
    vector<pair<int, int>> path;  // 用于记录路径
};

在 bfs 中，

构造一个节点队列，使用 queue 实现 BFS。队列先进先出，可以保证先处理离起点较近的节点。

将起点 （0，0） 入队，初始化步数为 0，路径为 { {0，0} } 。

标记起点 （0，0） 为已访问。

只要队列不为空，就继续循环处理每个节点。

void bfs() {
    queue<Node> q;  //构造节点队列
    q.push({0, 0, 0, {{0, 0}}});  // 起点入队
    v[0][0] = 1;  // 标记起点已访问

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

在循环中，首先检查当前节点是否是终点（n-1，m-1）。如果是，则输出路径 curr.path 中的每个坐标并结束函数。由于 BFS 保证第一次找到的就是最短路径，因此可以立即返回。

如果不懂这种输出方式的话，可以参考我写的这篇 范围for循环-CSDN博客

        if (curr.x == n - 1 && curr.y == m - 1) {  // 到达终点
            for (const auto& p : curr.path) {  //输出最短路径
                cout << "(" << p.first << "," << p.second << ")" << endl;
            }
            return;
        }

通过 dx 和 dy 遍历上下左右四个方向，计算新位置 (tx, ty)。如果新位置在迷宫范围内（tx >= 0 && tx < n && ty >= 0 && ty < m）且没有访问过（v[tx][ty] == 0）且不是障碍物（map[tx][ty] == 0），则将新位置标记为已访问，并在当前路径 curr.path 的基础上创建新的路径 newPath，将 (tx, ty) 加入路径中，将 (tx, ty) 作为新节点入队、步数加一、newPath 作为新路径。

for (int i = 0; i < 4; ++i) {  //依次遍历当前节点的相邻节点
    int tx = curr.x + dx[i];
    int ty = curr.y + dy[i];

    //如果当前节点满足条件：在迷宫范围内 && 未被访问 && 不是障碍物
    if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[tx][ty] == 0 && map[tx][ty] == 0){                
        v[tx][ty] = 1;  //标记为已访问
        vector<pair<int, int>> newPath = curr.path;  //继承当前路径
        newPath.push_back({tx, ty});  //把自己加入路径
        q.push({tx, ty, curr.step + 1, newPath});   //就将该节点入队，等待访问
    }
}

层层扩展，保证第一个到达终点的路径就是最短路径，找到后便可跳出循环。在每个节点的路径 path 中保存所经过的坐标，便于最终输出路径。

完整代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m;  //迷宫大小
int map[11][11] = {0};  //0表示可以走，1表示障碍物
int v[11][11] = {0};    //访问标记
int dx[4] = {0, 1, 0, -1};  //移动增量
int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, step;  //当前点坐标，到起点步数
    vector<pair<int, int>> path;  // 用于记录路径
};

void bfs() {
    queue<Node> q;  //构造节点队列
    q.push({0, 0, 0, {{0, 0}}});  //起点入队
    v[0][0] = 1;  //标记起点已访问

    while (!q.empty()) {
        Node curr = q.front();  //访问队头元素，出队
        q.pop();

        if (curr.x == n - 1 && curr.y == m - 1) {  //到达终点
            for (const auto& p : curr.path) //输出最短路径
                cout << "(" << p.first << "," << p.second << ")" << endl;
            return;
        }

        for (int i = 0; i < 4; ++i) {  //依次遍历当前节点的相邻节点
            int tx = curr.x + dx[i];
            int ty = curr.y + dy[i];

            //如果当前节点满足条件：在迷宫范围内 && 未被访问 && 不是障碍物
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && v[tx][ty] == 0 && map[tx][ty] == 0){                
                v[tx][ty] = 1;  //标记为已访问
                vector<pair<int, int>> newPath = curr.path;  //继承当前路径
                newPath.push_back({tx, ty});  //把自己加入路径
                q.push({tx, ty, curr.step + 1, newPath});   //就将该节点入队，等待访问
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];

    if (map[0][0] == 1) {
        cout << "No path exists." << endl;
        return 0;
    }

    bfs();
    return 0;
}