C语言数据结构之迷宫问题

迷宫问题是一种基本的搜索问题，其中需要在一个矩阵中寻找从起点到终点的路径。在本篇文章中，我们将以C语言为例，介绍迷宫问题的完整攻略。

准备工作

在开始之前，我们先要准备好数据结构。为了表示迷宫，我们使用一个二维数组。其中，0表示可以通过的路，1表示障碍物不可通过。为了记录路径，我们还需要使用一个二维数组来表示每个格子是否已经被访问过。

#define M 10 //迷宫的行数
#define N 10 //迷宫的列数

int maze[M][N] = {
    {0, 1, 0, 0, 0, 1, 0, 1, 0, 0}, 
    {0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 1, 1, 1, 0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
    {0, 1, 0, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 0, 1, 1, 1, 0}
};

int visited[M][N] = {0}; //所有格子未被访问过

搜索算法

接下来我们需要实现搜索算法，寻找从起点到终点的路径。在这里我们使用深度优先搜索算法（DFS）来实现。我们参数为当前位置的行和列，以及目标位置的行和列。

int dfs(int x, int y, int target_x, int target_y) {
    if (x == target_x && y == target_y) //找到路径，返回1
        return 1;
    if (x < 0 || x >= M || y < 0 || y >= N) //越界，返回0
        return 0;
    if (maze[x][y] == 1 || visited[x][y] == 1) //撞到墙或者已经访问过，返回0
        return 0;
    visited[x][y] = 1; //标记格子已被访问
    if (dfs(x-1, y, target_x, target_y) == 1) //向上搜索
        return 1;
    if (dfs(x+1, y, target_x, target_y) == 1) //向下搜索
        return 1;
    if (dfs(x, y-1, target_x, target_y) == 1) //向左搜索
        return 1;
    if (dfs(x, y+1, target_x, target_y) == 1) //向右搜索
        return 1;
    visited[x][y] = 0; //恢复格子未被访问
    return 0; //找不到路径，返回0
}

主函数

最后，我们在主函数中调用上面的dfs函数。以下是寻找从起点(2, 0)到终点(9, 9)的完整代码，并输出路径。

#include <stdio.h>

int main() {
    int start_x = 2, start_y = 0; //起点
    int target_x = 9, target_y = 9; //终点
    int path_found = dfs(start_x, start_y, target_x, target_y);
    if (path_found) {
        printf("Path from (%d,%d) to (%d,%d):\n", start_x,start_y,target_x,target_y);
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] == 1)
                    printf("(%d,%d) ", i, j);
            }
        }
    } else {
        printf("Path not found\n");
    }
    return 0;
}

示范运行

我们以两个示例来说明迷宫问题的求解过程。

示例一：从起点(1,1)到终点(10,10)

迷宫:

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

输出：

Path from (1,1) to (10,10):
(1,1) (1,2) (2,2) (3,2) (3,3) (3,4) (3,5) (2,5) (2,6) (1,6) (1,7) (1,8) (2,8) (3,8) (3,9) (3,10) (4,10) (5,10) (6,10) (7,10) (7,9) (8,9) (8,8) (9,8) (10,8) (10,9) (10,10)

示例二：从起点(3,8)到终点(3,1)

迷宫:

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

输出：

Path from (3,8) to (3,1):
(3,8) (2,8) (1,8) (1,7) (1,6) (2,6) (3,6) (4,6) (4,7) (4,8) (3,8) (3,7) (3,6) (3,5) (3,4) (4,4) (5,4) (5,3) (4,3) (3,3) (2,3) (2,2) (3,2) (3,1)