C++实现bfs迷宫问题最短路径

以下是一个简单的C代码实现bfs迷宫问题最短路径：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_ROW 10
#define MAX_COL 10

typedef struct {
    int row, col, parent;
} Node;

Node queue[MAX_ROW * MAX_COL];
int head = 0, tail = 0;

char maze[MAX_ROW][MAX_COL+1] = {
    "#S######.#",
    "......#..#",
    ".#.##.##.#",
    ".#........",
    "##.##.####",
    "....#....#",
    ".######.#.",
    "........#.",
    ".#######.#",
    "....#...G#"
};

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};

void enqueue(Node n) {
    queue[tail++] = n;
}

Node dequeue() {
    return queue[head++];
}

bool is_empty() {
    return head == tail;
}

void print_path(Node n) {
    if (n.parent == -1) {
        printf("(%d, %d)\n", n.row, n.col);
    } else {
        print_path(queue[n.parent]);
        printf("(%d, %d)\n", n.row, n.col);
    }
}

void bfs() {
    Node start = {0, 1, -1};
    enqueue(start);
    maze[start.row][start.col] = '#';

    while (!is_empty()) {
        Node current = dequeue();
        if (maze[current.row][current.col] == 'G') {
            print_path(current);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = current.row + dr[i];
            int nc = current.col + dc[i];

            if (nr < 0 || nc < 0 || nr >= MAX_ROW || nc >= MAX_COL) {
                continue;
            }

            if (maze[nr][nc] == '#' || maze[nr][nc] == 'S') {
                continue;
            }

            Node next = {nr, nc, head-1};
            enqueue(next);
            maze[nr][nc] = '#';
        }
    }
}

int main() {
    bfs();
    return 0;
}

这个代码使用了一个队列来实现bfs。在每次循环中，它从队列中取出一个节点，检查它是否是终点（G），如果是，就打印路径并结束程序。否则，它会检查节点周围的四个邻居，如果邻居是可通行的，就将它们加入队列中。如果队列为空，就说明没有从起点到达终点的路径。