递归回溯算法生成迷宫c语言
时间: 2023-07-24 17:41:20 浏览: 61
好的,下面是递归回溯算法生成迷宫的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define ROW 15 // 迷宫行数
#define COL 15 // 迷宫列数
int maze[ROW][COL]; // 迷宫数组,0 表示墙,1 表示路
int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
// 判断一个点是否在迷宫内
bool is_inside(int x, int y) {
return x >= 0 && x < ROW && y >= 0 && y < COL;
}
// 递归回溯生成迷宫
void generate_maze(int x, int y) {
int i, j, rand_dir, rand_idx;
int next_x, next_y;
// 随机打乱方向
for (i = 0; i < 4; i++) {
rand_idx = rand() % 4;
rand_dir = direction[i][0];
direction[i][0] = direction[rand_idx][0];
direction[rand_idx][0] = rand_dir;
rand_dir = direction[i][1];
direction[i][1] = direction[rand_idx][1];
direction[rand_idx][1] = rand_dir;
}
// 尝试四个方向
for (i = 0; i < 4; i++) {
next_x = x + direction[i][0] * 2;
next_y = y + direction[i][1] * 2;
if (is_inside(next_x, next_y) && maze[next_x][next_y] == 0) {
maze[next_x][next_y] = 1; // 打通障碍
maze[x + direction[i][0]][y + direction[i][1]] = 1;
generate_maze(next_x, next_y);
}
}
}
int main() {
int i, j;
// 初始化迷宫
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
maze[i][j] = 0;
}
}
// 随机生成起点和终点
srand(time(NULL));
int start_x = rand() % ROW;
int start_y = rand() % COL;
maze[start_x][start_y] = 1;
int end_x = rand() % ROW;
int end_y = rand() % COL;
maze[end_x][end_y] = 1;
// 生成迷宫
generate_maze(start_x, start_y);
// 输出迷宫
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (maze[i][j] == 0) {
printf("▇");
} else if (i == start_x && j == start_y) {
printf("S");
} else if (i == end_x && j == end_y) {
printf("E");
} else {
printf(" ");
}
}
printf("\n");
}
return 0;
}
```
该程序使用了递归回溯算法生成迷宫,并使用了随机打乱方向和随机生成起点和终点的方法增加了随机性。最后输出迷宫,墙用 "▇" 表示,起点用 "S" 表示,终点用 "E" 表示。