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 1 1 1
1 0 0 0 1
1 1 0 0 1
1 0 0 0 1
1 1 1 1 1

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

(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

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

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

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