C语言使用深度优先搜索算法解决迷宫问题 (堆栈)

什么是深度优先搜索算法

深度优先搜索算法 (DFS) 是一种常见的搜索算法。深度优先搜索算法像探险家一样从起点往前走，如果碰到了障碍物就返回，再尝试另一条路径。这个过程就是递归。

在深度优先搜索算法中，我们需要利用堆栈结构来保存需要回溯的节点。在搜索过程中，我们访问每个相邻的顶点，并将已经访问过的标记为已访问。然后我们继续访问相邻的节点，并标记已访问，如此下去，直到找到我们需要的节点，或是到达终点。

迷宫问题

假设我们有一个 n 行 m 列的迷宫，为了通行方便，我们将道路和墙都画成了矩阵，矩阵里的数字表示他的属性。其中，0 表示道路，1 表示墙，2 表示起点，3 表示终点。

我们需要使用深度优先搜索算法，在这个迷宫中找出一条从起点到终点的路径。

以下是一个 6x6 的迷宫示例：

1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1

起点为 (1, 1)，终点为 (4, 4)。

解决迷宫问题

我们可以使用一个二维数组来表示迷宫，并初始化起点和终点的坐标：

#define MAX_ROW 6
#define MAX_COL 6
int maze[MAX_ROW][MAX_COL] = {
    {1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 1},
    {1, 0, 1, 1, 0, 1},
    {1, 0, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1}
};

// 起点和终点
int start_row = 1, start_col = 1;
int end_row = 4, end_col = 4;

我们还需要一个 stack 数据结构，用于保存需要回溯的节点：

#define MAX_SIZE 100
typedef struct {
    int row;
    int col;
} element;

// 定义堆栈
element stack[MAX_SIZE];
int top = -1;

// 入栈操作
void push(int row, int col) {
    element e = {row, col};
    stack[++top] = e;
}

// 出栈操作
element pop() {
    return stack[top--];
}

// 判断堆栈是否为空
int is_empty() {
    return top == -1;
}

在我们开启搜索之前，我们需要将起点压入堆栈，并将起点标记为已访问：

// 标记已访问
int visited[MAX_ROW][MAX_COL] = {0};
visited[start_row][start_col] = 1;

// 将起点入栈
push(start_row, start_col);

接下来，我们需要编写一个函数来搜索迷宫。这个函数的任务是，从堆栈中取出一个节点，检查它是否是终点，如果不是，则检查它的四个相邻节点是否可以访问。如果可以访问，则将这个节点压入堆栈，并标记为已访问。

如果堆栈为空，说明我们已经走到了迷宫的边缘，但是没有找到终点。这个时候，我们需要返回 0，表示没有找到出路。

int search() {
    while (!is_empty()) {
        element e = pop();

        // 判断是否到达终点
        if (e.row == end_row && e.col == end_col) {
            printf("(%d, %d)\n", e.row, e.col);
            return 1;
        }

        // 取出当前节点的四个相邻节点，如果可以访问，则入栈
        if (e.row - 1 >= 0 && maze[e.row - 1][e.col] == 0 && !visited[e.row - 1][e.col]) {
            element adj = {e.row - 1, e.col};
            push(adj.row, adj.col);
            visited[adj.row][adj.col] = 1;
        }
        if (e.col - 1 >= 0 && maze[e.row][e.col - 1] == 0 && !visited[e.row][e.col - 1]) {
            element adj = {e.row, e.col - 1};
            push(adj.row, adj.col);
            visited[adj.row][adj.col] = 1;
        }
        if (e.row + 1 < MAX_ROW && maze[e.row + 1][e.col] == 0 && !visited[e.row + 1][e.col]) {
            element adj = {e.row + 1, e.col};
            push(adj.row, adj.col);
            visited[adj.row][adj.col] = 1;
        }
        if (e.col + 1 < MAX_COL && maze[e.row][e.col + 1] == 0 && !visited[e.row][e.col + 1]) {
            element adj = {e.row, e.col + 1};
            push(adj.row, adj.col);
            visited[adj.row][adj.col] = 1;
        }

        printf("(%d, %d)\n", e.row, e.col);
    }
    return 0;
}

最后，我们只需要在主函数中调用 search 函数即可：

int main() {
    if (search()) {
        printf("找到了出路\n");
    } else {
        printf("没有出路\n");
    }
    return 0;
}

示例说明

假设我们要在以下这个迷宫中寻找一条从起点 (1, 1) 到终点 (4, 4) 的路径：

我们可以使用上面的代码进行搜索，得到的输出为：

(1, 1)
(2, 1)
(3, 1)
(4, 1)
(4, 2)
(4, 3)
(3, 3)
(2, 3)
(1, 3)
(1, 2)
(2, 2)
(3, 2)
(4, 4)
找到了出路

说明我们已经成功找到了一条从起点到终点的路径。

再举一个例子，假设我们要在以下这个迷宫中寻找一条从起点 (1, 1) 到终点 (5, 5) 的路径：

1 1 1 1 1 1
1 0 1 0 0 1
1 0 1 0 1 1
1 0 1 0 0 1
1 0 0 0 1 1
1 1 1 1 1 1