分别用广度优先和深度优先解决迷宫问题c语言

好的，下面是分别用广度优先和深度优先解决迷宫问题的 C 语言代码，供参考：

### 广度优先搜索

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

#define ROW 5
#define COL 5

int maze[ROW][COL] = {
    {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}
};

bool visited[ROW][COL];

typedef struct {
    int x;
    int y;
    int prev;
} Point;

Point queue[ROW * COL];
int front = -1, rear = -1;

void enqueue(Point p) {
    if (front == -1) {
        front++;
    }
    queue[++rear] = p;
}

Point dequeue() {
    if (front > rear) {
        printf("Queue is empty!");
        exit(1);
    }
    return queue[front++];
}

bool is_valid(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) {
        return false;
    }
    if (maze[x][y] == 1 || visited[x][y]) {
        return false;
    }
    return true;
}

void print_path(Point p) {
    if (p.prev == -1) {
        printf("(%d, %d)", p.x, p.y);
        return;
    }
    print_path(queue[p.prev]);
    printf(" -> (%d, %d)", p.x, p.y);
}

void bfs(int x, int y) {
    visited[x][y] = true;
    Point start = {x, y, -1};
    enqueue(start);
    while (front <= rear) {
        Point curr = dequeue();
        if (curr.x == ROW - 1 && curr.y == COL - 1) {
            print_path(curr);
            return;
        }
        int x_dir[] = {-1, 0, 1, 0};
        int y_dir[] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int next_x = curr.x + x_dir[i];
            int next_y = curr.y + y_dir[i];
            if (is_valid(next_x, next_y)) {
                visited[next_x][next_y] = true;
                Point next = {next_x, next_y, front - 1};
                enqueue(next);
            }
        }
    }
    printf("No path found!");
}

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

### 深度优先搜索

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

#define ROW 5
#define COL 5

int maze[ROW][COL] = {
    {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}
};

bool visited[ROW][COL];

bool dfs(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) {
        return false;
    }
    if (maze[x][y] == 1 || visited[x][y]) {
        return false;
    }
    visited[x][y] = true;
    if (x == ROW - 1 && y == COL - 1) {
        printf("(%d, %d)", x, y);
        return true;
    }
    if (dfs(x - 1, y) || dfs(x, y + 1) || dfs(x + 1, y) || dfs(x, y - 1)) {
        printf(" -> (%d, %d)", x, y);
        return true;
    }
    return false;
}

int main() {
    if (!dfs(0, 0)) {
        printf("No path found!");
    }
    return 0;
}

以上两段代码都是基于同样的 5x5 迷宫，其中 0 表示可以通过，1 表示不能通过。广度优先搜索使用了队列，在每次取出队首元素时，将其合法的相邻点加入队列，并标记为已访问。深度优先搜索使用递归的方式，依次搜索当前点的四周点，如果其中有一条路能到达终点，则输出路径。