dfs生成迷宫c语言

深度优先搜索(Depth First Search, DFS)是一种用于图和树的遍历算法。它可以用来生成迷宫。下面是一个用C语言实现DFS迷宫生成的简单示例程序：

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

// 定义迷宫的行数和列数
#define ROW 10
#define COL 10

// 定义迷宫的墙壁和路径符号
#define WALL '#'
#define PATH ' '

// 定义四个方向的移动向量：上、右、下、左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

char maze[ROW][COL]; // 迷宫地图

// 初始化迷宫地图，所有位置都设置为墙壁
void initMaze() {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            maze[i][j] = WALL;
        }
    }
}

// 检查位置(x, y)是否在迷宫范围内
int isValid(int x, int y) {
    return (x >= 0 && x < ROW && y >= 0 && y < COL);
}

// 以点(x, y)为起点，进行DFS遍历生成迷宫
void DFS(int x, int y) {
    maze[x][y] = PATH; // 将当前位置标记为路径
    
    // 随机打乱四个方向的顺序
    int dirs[4] = {0, 1, 2, 3};
    for (int i = 0; i < 4; i++) {
        int j = rand() % 4;
        int temp = dirs[i];
        dirs[i] = dirs[j];
        dirs[j] = temp;
    }
    
    // 在四个方向上进行探索
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[dirs[i]];
        int ny = y + dy[dirs[i]];
        
        // 判断新位置(nx, ny)是否有效及是否是墙壁
        if (isValid(nx, ny) && maze[nx][ny] == WALL) {
            int wallCount = 0; // 统计周围的墙壁数量
            for (int j = 0; j < 4; j++) {
                int adjX = nx + dx[j];
                int adjY = ny + dy[j];
                if (isValid(adjX, adjY) && maze[adjX][adjY] == WALL) {
                    wallCount++;
                }
            }
            
            // 如果周围有多于1个的墙壁，则打通新位置(nx, ny)
            if (wallCount >= 2) {
                maze[nx][ny] = PATH;
                DFS(nx, ny); // 递归探索新位置
            }
        }
    }
}

// 打印迷宫地图
void printMaze() {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%c ", maze[i][j]);
        }
        printf("\n");
    }
}

int main() {
    srand(time(0)); // 设置随机数种子，以保证每次生成的迷宫都不一样
    
    initMaze(); // 初始化迷宫地图
    DFS(0, 0); // 以起点(0, 0)开始进行DFS生成迷宫
    printMaze(); // 打印迷宫地图
    
    return 0;
}

这是一个简单的使用DFS算法生成迷宫的示例程序。该程序使用一个二维字符数组`maze`来表示迷宫地图，`'#'`表示墙壁，`' '`表示路径。通过递归调用`DFS`函数，从起点开始生成迷宫。在`DFS`函数中，首先将当前位置标记为路径，然后随机打乱四个方向的顺序，从每个方向上递归探索新的位置，直到所有位置都被访问完毕。最后，调用`printMaze`函数打印生成的迷宫地图。