C++ 基于BFS算法的走迷宫自动寻路的实现攻略

算法介绍

BFS即广度优先搜索，它的主要思想是从起点出发，依次访问离起点最近的所有未访问的节点。它除了可以用于寻路，也可以用于其他需要搜索的问题中。在Maze寻路问题中，把所有可能走的路线一个个枚举出来，找到最短的一条。

实现步骤

1. 定义节点

定义一个节点，它包含迷宫的当前位置，当前步数，以及该位置的前一步位置。例如：

struct Node {
    int x;
    int y;
    int step;
    int pre;
};

2. 生成地图

可以使用二维数组来表示地图，0表示可以通过的路，1表示障碍物。例如：

int map[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
};

3. 定义搜索方向

因为搜索方向有上下左右四个方向，所以可以定义dx和dy来表示每个方向的移动情况。例如：

int dx[4] = {0, 1, 0, -1};  // x轴移动
int dy[4] = {1, 0, -1, 0};  // y轴移动

4. 实现BFS算法

从起点出发，依次访问从当前位置可到达的所有未被访问的节点，并计算它们到起点的步数，最后找到终点的位置和步数。

void bfs() {
    queue<Node> q;
    Node start = {0, 0, 0, -1};
    q.push(start);
    visited[0][0] = true;

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

        if (cur.x == endX && cur.y == endY) {  // 到达终点
            printf("到达终点，步数为：%d\n路径为：", cur.step);
            printRoute(cur.pre);
            return;
        }

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

            if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 1 || visited[nx][ny]) {
                continue;  // 越界或障碍物或已经访问过
            }

            visited[nx][ny] = true;
            Node next = {nx, ny, cur.step + 1, q.size()-1};  // 记录前一步下标
            q.push(next);
        }
    }
}

5. 输出路径

找到终点后，可以通过记录每个节点的前一节点下标位置，递归输出路径。

void printRoute(int pre) {
    if (pre == -1) {
        return;
    }

    printRoute(q[pre].pre);
    printf("(%d, %d) ", q[pre].x, q[pre].y);
}

示例说明

示例一

图示：

S：起点
E：终点
0：可以通过的路
1：障碍物

代码示例：

#include <iostream>
#include <queue>

using namespace std;

const int N = 110;

int map[N][N];
bool visited[N][N];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Node {
    int x;
    int y;
    int step;
    int pre;
};

vector<Node> q;

int n, m;
int startX, startY, endX, endY;

void bfs();
void printRoute(int pre);

int main() {
    cin >> n >> m >> startX >> startY >> endX >> endY;

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

    bfs();

    return 0;
}

void bfs() {
    queue<Node> q;
    Node start = {startX, startY, 0, -1};
    q.push(start);
    visited[startX][startY] = true;

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

        if (cur.x == endX && cur.y == endY) {
            printf("到达终点，步数为：%d\n路径为：", cur.step);
            printRoute(cur.pre);
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 1 || visited[nx][ny]) {
                continue;
            }

            visited[nx][ny] = true;
            Node next = {nx, ny, cur.step + 1, q.size()-1};
            q.push(next);
        }
    }
}

void printRoute(int pre) {
    if (pre == -1) {
        return;
    }

    printRoute(q[pre].pre);
    printf("(%d, %d) ", q[pre].x, q[pre].y);
}

输入样例：

5 5 0 0 4 3
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

到达终点，步数为：9
路径为：(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4)

示例二

图示：

S：起点
E：终点
0：可以通过的路
1：障碍物