C++ 迷宫路径查找算法实现 - 深度优先搜索

C++ 迷宫路径查找算法实现 - 深度优先搜索

本文介绍使用 C++ 实现的迷宫路径查找算法，使用深度优先搜索 (DFS) 算法找出从迷宫入口到出口的所有路径，并输出路径总数。

代码示例

#include <iostream>
#include <vector>

using namespace std;

// 定义迷宫的大小
const int N = 5;

// 定义迷宫的格子
int maze[N][N] = {
    {0, 0, 0, 0, 0},
    {1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}
};

// 定义路径的结构体
struct Point {
    int x;
    int y;
};

// 定义路径集合
vector<vector<Point>> paths;

// 定义当前路径
vector<Point> currentPath;

// 判断当前位置是否合法
bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0;
}

// 深度优先搜索查找路径
void dfs(int x, int y) {
    // 判断当前位置是否为出口
    if (x == 0 && y == N - 1) {
        paths.push_back(currentPath);
        return;
    }

    // 定义八个方向的偏移量
    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

    // 尝试八个方向
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 判断新位置是否合法
        if (isValid(nx, ny)) {
            // 标记当前位置已访问
            maze[nx][ny] = 1;

            // 添加新位置到当前路径中
            currentPath.push_back({nx, ny});

            // 递归搜索新位置
            dfs(nx, ny);

            // 恢复当前位置为未访问
            maze[nx][ny] = 0;

            // 移除当前路径中的最后一个位置
            currentPath.pop_back();
        }
    }
}

int main() {
    // 初始化当前路径
    currentPath.push_back({0, 0});

    // 搜索路径
    dfs(0, 0);

    // 输出路径总数
    cout << '路径总数：' << paths.size() << endl;

    // 输出所有路径
    for (int i = 0; i < paths.size(); i++) {
        cout << '路径' << i + 1 << ':';
        for (int j = 0; j < paths[i].size(); j++) {
            cout << '(' << paths[i][j].x << ', ' << paths[i][j].y << ')';
            if (j != paths[i].size() - 1) {
                cout << ' -> ';
            }
        }
        cout << endl;
    }

    return 0;
}

代码解析

1. 迷宫定义:

   • 使用二维数组 maze 表示迷宫，0 代表可通行的格子，1 代表不可通行的格子。
   • N 定义迷宫的大小，这里示例为 5x5 的迷宫。

2. 路径结构:

   • 使用 Point 结构体表示迷宫中的一个格子坐标，包含 x 和 y 两个成员变量。
   • 使用 vector<vector<Point>> paths 存储所有找到的路径，每个路径是一个 Point 坐标的向量。
   • 使用 vector<Point> currentPath 存储当前正在搜索的路径。

3. 合法性判断:

   • isValid(x, y) 函数判断给定坐标 (x, y) 是否合法，即是否在迷宫范围内且该格子是可通行的。

4. 深度优先搜索:

   • dfs(x, y) 函数实现深度优先搜索，从给定坐标 (x, y) 开始，尝试八个方向的移动，递归搜索所有可行的路径。
   • 算法的核心思路是：
     • 如果当前位置是出口，则将当前路径加入 paths 中。
     • 否则，尝试八个方向，如果新位置合法，则将新位置加入当前路径，并递归搜索新位置。
     • 递归返回后，需要将当前位置恢复为可通行状态，并移除当前路径中的最后一个位置。

5. 主函数:

   • 初始化当前路径 currentPath 为入口位置。
   • 调用 dfs(0, 0) 函数开始搜索路径。
   • 输出路径总数和所有找到的路径。

总结

本文提供了一个使用 C++ 实现迷宫路径查找算法的示例，使用深度优先搜索 (DFS) 算法找到所有从入口到出口的路径。你可以根据实际情况修改迷宫的大小和格子的布局，然后编译运行该程序。程序将输出路径的总数以及所有的路径。