C语言 迷宫问题（任意生成地图，展示路径）
#include
#include
#include void generateMaze(char **maze, int rows, int cols) {// 初始化迷宫地图为全部为 '#'for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {maze[i][j] = '#';}}// 随机选择起点和终点（位置不能在边界上）srand((unsigned int) time(NULL));int start_x, start_y, dest_x, dest_y;do {start_x = rand() % (rows - 2) + 1;start_y = rand() % (cols - 2) + 1;dest_x = rand() % (rows - 2) + 1;dest_y = rand() % (cols - 2) + 1;} while (start_x == dest_x && start_y == dest_y);// 生成迷宫maze[start_x][start_y] = ' '; // 起点设为可走maze[dest_x][dest_y] = ' '; // 终点设为可走int visited[rows][cols];for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {visited[i][j] = 0;}}int dx[4] = {-1, 0, 1, 0}; // 向四个方向移动int dy[4] = {0, 1, 0, -1};int stack_x[rows * cols], stack_y[rows * cols]; // 模拟栈，用于回溯int top = 0;stack_x[top] = start_x;stack_y[top] = start_y;visited[start_x][start_y] = 1;while (top >= 0) {int x = stack_x[top];int y = stack_y[top];int flag = 0;for (int i = 0; i < 4; i++) {int new_x = x + dx[i];int new_y = y + dy[i];if (new_x >= 1 && new_x < rows - 1 && new_y >= 1 && new_y < cols - 1 &&maze[new_x][new_y] == '#' && visited[new_x][new_y] == 0) {flag = 1;break;}}if (flag) {int r = rand() % 4;int new_x = x + dx[r];int new_y = y + dy[r];if (new_x >= 1 && new_x < rows - 1 && new_y >= 1 && new_y < cols - 1 &&maze[new_x][new_y] == '#' && visited[new_x][new_y] == 0) {maze[(x+new_x)/2][(y+new_y)/2] = ' '; // 打通两个相邻格子之间的墙visited[new_x][new_y] = 1;stack_x[++top] = new_x;stack_y[top] = new_y;}} else {top--;}}
}void printMaze(char **maze, int rows, int cols) {for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {printf("%c", maze[i][j]);}printf("\n");}
}void dfs(char **maze, int rows, int cols, int x, int y, int dest_x, int dest_y, int **visited, int *path_x, int *path_y, int *path_len) {if (x == dest_x && y == dest_y) {*path_len += 1;path_x[*path_len] = x;path_y[*path_len] = y;return;}visited[x][y] = 1;int dx[4] = {-1, 0, 1, 0}; // 向四个方向移动int dy[4] = {0, 1, 0, -1};for (int i = 0; i < 4; i++) {int new_x = x + dx[i];int new_y = y + dy[i];if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols &&maze[new_x][new_y] == ' ' && visited[new_x][new_y] == 0) {*path_len += 1;path_x[*path_len] = x;path_y[*path_len] = y;dfs(maze, rows, cols, new_x, new_y, dest_x, dest_y, visited, path_x, path_y, path_len);*path_len -= 1;}}
}int main() {int rows, cols;printf("请输入迷宫的行数和列数：");scanf("%d %d", &rows, &cols);char **maze = (char **) malloc(rows * sizeof(char *));for (int i = 0; i < rows; i++) {maze[i] = (char *) malloc(cols * sizeof(char));}generateMaze(maze, rows, cols);printMaze(maze, rows, cols);// 求解路径int **visited = (int **) malloc(rows * sizeof(int *));for (int i = 0; i < rows; i++) {visited[i] = (int *) malloc(cols * sizeof(int));for (int j = 0; j < cols; j++) {visited[i][j] = 0;}}int path_x[rows * cols], path_y[rows * cols], path_len = -1;dfs(maze, rows, cols, 1, 1, rows-2, cols-2, visited, path_x, path_y, &path_len);// 输出路径printf("\n正确路径：\n");for (int i = path_len; i >= 0; i--) {maze[path_x[i]][path_y[i]] = '*';}printMaze(maze, rows, cols);// 释放动态分配的内存for (int i = 0; i < rows; i++) {free(maze[i]);free(visited[i]);}free(maze);free(visited);return 0;
}
首先通过 scanf 函数读入迷宫的行数和列数，然后动态分配二维字符数组 maze 以保存迷宫地图。生成迷宫的函数 generateMaze 中，我们增加了两个参数 rows 和 cols，表示迷宫的行数和列数，同时为了避免溢出，使用了动态分配的 visited 数组来代替固定大小的数组。
dfs 函数来实现深度优先搜索，用于求解从起点到终点的路径。在 dfs 函数中，我们首先判断当前点是否为终点，如果是则将其加入路径数组；否则遍历当前点的四个相邻格子，找到可通行的格子并递归搜索下去。在搜索结束后，需要将 visited 数组恢复到原始状态，以便下一次搜索使用。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！