迷宫问题c语言dfs算法代码

在C语言中，深度优先搜索（Depth-First Search，DFS）是一个用于解决迷宫问题的经典算法。以下是一个简单的DFS解决方案的伪代码和概述：

#include <stdio.h>
#include <stdbool.h>

// 假设迷宫用二维字符数组maze表示，'0'表示空格，'1'表示墙壁
bool is_valid(int x, int y, int maze[ROW][COL], bool visited[]) {
    // 检查坐标是否越界和是否已被访问
    return x >= 0 && x < ROW && y >= 0 && y < COL && maze[x][y] == '0' && !visited[x][y];
}

// DFS遍历函数
bool dfs(int x, int y, int maze[ROW][COL], bool *visited) {
    visited[x][y] = true;
    printf("(%d,%d)", x, y); // 打印当前路径节点

    if (x == targetX && y == targetY) { // 到达目标点
        printf("Solution found!");
        return true;
    }

    // 搜索上下左右邻居
    if (is_valid(x + 1, y, maze, visited)) dfs(x + 1, y, maze, visited);
    if (is_valid(x - 1, y, maze, visited)) dfs(x - 1, y, maze, visited);
    if (is_valid(x, y + 1, maze, visited)) dfs(x, y + 1, maze, visited);
    if (is_valid(x, y - 1, maze, visited)) dfs(x, y - 1, maze, visited);

    // 如果所有邻居都访问过了，但是没有到达目标，回溯
    if (!is_solution_found) visited[x][y] = false; // 取消当前节点标记，准备回溯
    return false;
}

int main() {
    // 初始化迷宫和访问标志数组
    int maze[ROW][COL], targetX, targetY;
    // ... 填充迷宫和目标位置
    bool visited[ROW][COL] = {false}; // 初始化为未访问

    dfs(startX, startY, maze, visited); // 从起点开始搜索
    return 0;
}