prim算法迷宫c语言

以下是使用prim算法生成迷宫的C语言代码：

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

#define ROW 10  // 迷宫行数
#define COLUMN 10  // 迷宫列数

// 迷宫单元格结构体
struct cell {
    int row;  // 行号
    int column;  // 列号
    int visited;  // 是否访问过
    int walls[4];  // 墙壁状态
    /*
        墙壁状态说明：
        walls[0]：上边墙壁，0表示未破坏，1表示已破坏
        walls[1]：右边墙壁，0表示未破坏，1表示已破坏
        walls[2]：下边墙壁，0表示未破坏，1表示已破坏
        walls[3]：左边墙壁，0表示未破坏，1表示已破坏
    */
};

// 初始化迷宫单元格
void init_cell(struct cell *c, int row, int column) {
    c->row = row;
    c->column = column;
    c->visited = 0;
    c->walls[0] = 1;
    c->walls[1] = 1;
    c->walls[2] = 1;
    c->walls[3] = 1;
}

// 获取迷宫单元格
struct cell *get_cell(struct cell *grid, int row, int column) {
    if (row < 0 || row >= ROW || column < 0 || column >= COLUMN) {
        return NULL;
    }
    return &grid[row * COLUMN + column];
}

// 获取迷宫单元格周围未访问的单元格
struct cell **get_unvisited_neighbors(struct cell *grid, int row, int column) {
    struct cell **neighbors = (struct cell **)malloc(4 * sizeof(struct cell *));
    int count = 0;

    struct cell *top = get_cell(grid, row - 1, column);
    if (top != NULL && !top->visited) {
        neighbors[count++] = top;
    }

    struct cell *right = get_cell(grid, row, column + 1);
    if (right != NULL && !right->visited) {
        neighbors[count++] = right;
    }

    struct cell *bottom = get_cell(grid, row + 1, column);
    if (bottom != NULL && !bottom->visited) {
        neighbors[count++] = bottom;
    }

    struct cell *left = get_cell(grid, row, column - 1);
    if (left != NULL && !left->visited) {
        neighbors[count++] = left;
    }

    if (count == 0) {
        free(neighbors);
        return NULL;
    } else {
        return neighbors;
    }
}

// 打印迷宫
void print_maze(struct cell *grid) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COLUMN; j++) {
            struct cell *c = get_cell(grid, i, j);
            // 打印左边墙壁
            if (c->walls[3]) {
                printf("|");
            } else {
                printf(" ");
            }
            // 打印空格
            if (i == 0 && j == 0) {
                printf("S");
            } else if (i == ROW - 1 && j == COLUMN - 1) {
                printf("E");
            } else {
                printf(" ");
            }
            // 打印右边墙壁
            if (c->walls[1]) {
                printf("|");
            } else {
                printf(" ");
            }
        }
        printf("\n");
        // 打印下边墙壁
        for (int j = 0; j < COLUMN; j++) {
            struct cell *c = get_cell(grid, i, j);
            if (c->walls[2]) {
                printf("--");
            } else {
                printf("  ");
            }
        }
        printf("\n");
    }
}

// prim算法生成迷宫
void generate_maze(struct cell *grid) {
    // 随机选择起始单元格
    struct cell *start = get_cell(grid, 0, 0);
    start->visited = 1;

    // 初始化候选边集合
    int edge_count = ROW * COLUMN - 1;
    struct cell **edges = (struct cell **)malloc(edge_count * sizeof(struct cell *));
    int index = 0;
    struct cell **neighbors = get_unvisited_neighbors(grid, start->row, start->column);
    for (int i = 0; i < 4 && neighbors != NULL && neighbors[i] != NULL; i++) {
        edges[index++] = neighbors[i];
    }
    free(neighbors);

    // 随机选择候选边并加入迷宫
    while (index > 0) {
        int random_index = rand() % index;
        struct cell *edge = edges[random_index];
        struct cell *neighbor = edge;
        struct cell *current = get_cell(grid, edge->row, edge->column);
        free(edges[random_index]);
        edges[random_index] = edges[--index];

        if (current->visited && !neighbor->visited) {
            // 破坏当前单元格与相邻单元格之间的墙壁
            if (current->row == neighbor->row) {
                if (current->column < neighbor->column) {
                    current->walls[1] = 0;  // 破坏当前单元格右侧墙壁
                    neighbor->walls[3] = 0;  // 破坏相邻单元格左侧墙壁
                } else {
                    current->walls[3] = 0;  // 破坏当前单元格左侧墙壁
                    neighbor->walls[1] = 0;  // 破坏相邻单元格右侧墙壁
                }
            } else {
                if (current->row < neighbor->row) {
                    current->walls[2] = 0;  // 破坏当前单元格下侧墙壁
                    neighbor->walls[0] = 0;  // 破坏相邻单元格上侧墙壁
                } else {
                    current->walls[0] = 0;  // 破坏当前单元格上侧墙壁
                    neighbor->walls[2] = 0;  // 破坏相邻单元格下侧墙壁
                }
            }
            // 将相邻单元格加入迷宫，并将其候选边加入候选边集合
            neighbor->visited = 1;
            neighbors = get_unvisited_neighbors(grid, neighbor->row, neighbor->column);
            for (int i = 0; i < 4 && neighbors != NULL && neighbors[i] != NULL; i++) {
                edges[index++] = neighbors[i];
            }
            free(neighbors);
        }
    }
    free(edges);
}

int main() {
    struct cell *grid = (struct cell *)malloc(ROW * COLUMN * sizeof(struct cell));
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COLUMN; j++) {
            init_cell(&grid[i * COLUMN + j], i, j);
        }
    }
    srand((unsigned int)time(NULL));
    generate_maze(grid);
    print_maze(grid);
    free(grid);
    return 0;
}