c语言迷宫生成prim算法

Prim算法是最小生成树算法之一，可以用来生成迷宫。

首先，我们需要定义一个迷宫的数据结构。可以使用一个二维数组来表示迷宫，其中0表示通路，1表示墙壁。例如：

int maze[HEIGHT][WIDTH] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
    {1, 0, 1, 0, 0, 0, 0, 1, 0, 1},
    {1, 0, 1, 0, 1, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

接下来，我们可以用Prim算法来生成迷宫。具体步骤如下：

1. 随机选择一个起点，将其加入一个集合S中。

2. 对于集合S中的每个点，找到所有与之相邻的点，并将其加入一个集合T中。

3. 在集合T中选择一条权值最小的边，将其加入生成树中，并将其所连接的点加入集合S中。

4. 重复步骤2和3，直到集合S中包含所有的点。

下面是一个使用Prim算法生成迷宫的示例代码：

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

#define WIDTH 10
#define HEIGHT 10

int maze[HEIGHT][WIDTH];

typedef struct {
    int x;
    int y;
} point;

int get_weight(point p1, point p2) {
    // 计算两个点之间的权值
    int dx = p1.x - p2.x;
    int dy = p1.y - p2.y;
    return dx * dx + dy * dy;
}

point get_random_point() {
    // 随机选择一个点作为起点
    point p;
    do {
        p.x = rand() % WIDTH;
        p.y = rand() % HEIGHT;
    } while (maze[p.y][p.x] == 1);
    return p;
}

void generate_maze() {
    // 使用Prim算法生成迷宫
    int i, j;
    point p, q;
    int weight, min_weight;
    point *candidates = malloc(sizeof(point) * WIDTH * HEIGHT);
    int num_candidates = 0;
    point *neighbors = malloc(sizeof(point) * 4);
    int num_neighbors;
    point *tree = malloc(sizeof(point) * WIDTH * HEIGHT);
    int num_tree = 0;
    srand(time(NULL));
    // 随机选择一个起点
    p = get_random_point();
    // 将起点加入生成树
    tree[num_tree++] = p;
    while (num_tree < WIDTH * HEIGHT) {
        // 找到所有与生成树相邻的点
        num_candidates = 0;
        for (i = 0; i < num_tree; i++) {
            p = tree[i];
            // 上下左右四个方向
            neighbors[0].x = p.x;
            neighbors[0].y = p.y - 1;
            neighbors[1].x = p.x;
            neighbors[1].y = p.y + 1;
            neighbors[2].x = p.x - 1;
            neighbors[2].y = p.y;
            neighbors[3].x = p.x + 1;
            neighbors[3].y = p.y;
            num_neighbors = 0;
            for (j = 0; j < 4; j++) {
                q = neighbors[j];
                if (q.x >= 0 && q.x < WIDTH && q.y >= 0 && q.y < HEIGHT && maze[q.y][q.x] == 0) {
                    candidates[num_candidates++] = q;
                }
            }
        }
        if (num_candidates == 0) {
            // 所有相邻的点都已经在生成树中了，无法继续生成迷宫
            break;
        }
        // 在相邻的点中选择权值最小的边
        min_weight = -1;
        for (i = 0; i < num_candidates; i++) {
            p = candidates[i];
            for (j = 0; j < num_tree; j++) {
                q = tree[j];
                weight = get_weight(p, q);
                if (min_weight == -1 || weight < min_weight) {
                    min_weight = weight;
                    neighbors[0] = p;
                    neighbors[1] = q;
                }
            }
        }
        // 将新的边加入生成树，并将相邻的点加入生成树
        tree[num_tree++] = neighbors[0];
        maze[neighbors[0].y][neighbors[0].x] = 1;
    }
    free(candidates);
    free(neighbors);
    free(tree);
}

void print_maze() {
    int i, j;
    for (i = 0; i < HEIGHT; i++) {
        for (j = 0; j < WIDTH; j++) {
            if (maze[i][j] == 1) {
                printf("  ");
            } else {
                printf("██");
            }
        }
        printf("\n");
    }
}

int main() {
    generate_maze();
    print_maze();
    return 0;
}

这个示例代码使用了一个point结构体来表示二维坐标，使用了一个candidates数组来存储与生成树相邻的点，使用了一个neighbors数组来存储相邻的点。在生成迷宫之前，先将所有的墙壁标记出来。在生成迷宫过程中，使用了一个tree数组来存储生成树，使用了一个num_tree变量来记录生成树中已经包含的点的个数。最后，使用print_maze函数来输出生成的迷宫。