迷宫问题数据结构c语言实现

在C语言中实现迷宫问题通常会使用广度优先搜索(Breadth-First Search, BFS)或者深度优先搜索(Deep-First Search, DFS)算法，特别是当涉及图论的问题时。下面是一个简单的二维数组表示的迷宫，使用BFS方法寻找从起点到终点的路径：

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

#define ROW 5 // 迷宫的行数
#define COL 5 // 迷宫的列数
#define START 0 // 起点索引
#define END   9 // 终点索引

typedef struct {
    int maze[ROW][COL];
    int visited[ROW][COL]; // 记录访问过的格子
} Maze;

int is_valid(int x, int y) { // 检查坐标是否有效
    return (x >= 0 && x < ROW && y >= 0 && y < COL && maze[x][y] == 0);
}

void bfs(Maze* maze, int start_x, int start_y) {
    int queue[ROW * COL], front = -1, rear = -1;
    maze->visited[start_x][start_y] = 1;
    queue[++rear] = start_x * COL + start_y; // 将起始位置入队

    while(front != rear) {
        int curr_x = queue[++front] / COL;
        int curr_y = queue[front] % COL;

        if(curr_x == END && curr_y == END) {
            printf("Path found: (%d,%d)\n", curr_x, curr_y);
            return;
        }

        // 四邻域检查并标记为已访问
        for(int dx = -1; dx <= 1; dx++) {
            for(int dy = -1; dy <= 1; dy++) {
                if(is_valid(curr_x + dx, curr_y + dy)) {
                    maze->visited[curr_x + dx][curr_y + dy] = 1;
                    queue[++rear] = curr_x + dx * COL + curr_y + dy;
                }
            }
        }
    }
    printf("No path found.\n");
}

int main() {
    Maze maze;
    // 初始化迷宫矩阵和访问矩阵
    for(int i=0; i<ROW; i++) {
        for(int j=0; j<COL; j++) {
            maze.maze[i][j] = (i==0 || i==ROW-1 || j==0 || j==COL-1) ? 1 : 0; // 1代表墙壁，0代表通道
        }
    }

    bfs(&maze, START/ROW, START%ROW); // 开始搜索
    return 0;
}

在这个例子中，我们创建了一个二维数组`maze`来表示迷宫，其中值为0的地方是可以通过的通道，1则是墙壁。通过BFS，我们可以找到从起点到终点的最短路径。如果找不到路径，程序会打印"No path found."。