C语言实现【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。 image.png 找到迷宫从起点到终点的所有路径中最短的一条，输出最短路径的长度。如果从起点到终点没有路径，则输出NO PASS! 注：所有迷宫的起点为左上角，终点为右下角。 【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。 【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。 【样例输入】 0101101 0000001 1001101 0010001 1010101 0000000 【样例输出】 11 【样例说明】 迷宫总共有8条路径： DRDDDDRRRRR DRDDDDRRUURRDDR DRDRURRRDDDDR DRDRURRRDDLLDDRRR DRRDLDDDRRRRR DRRDLDDDRRUURRDDR DRRRRRDDDDR DRRRRRDDLLDDRRR 其中有两条最短路径DRDDDDRRRRR和DRRRRRDDDDR，所以输出最短路径的长度，即字符串的长度，11 输出数值：11

以下是C语言的实现代码，使用了队列来辅助搜索过程：

#include <stdio.h>
#include <string.h>

#define MAXN 1000
#define MAXM 1000
#define INF 0x3f3f3f3f

// 定义迷宫结构体
struct Maze {
    int n, m;           // 迷宫的行数和列数
    char s[MAXN][MAXM]; // 迷宫的字符数组
    int vis[MAXN][MAXM];// 每个节点是否访问过
    int dis[MAXN][MAXM];// 节点到起点的距离
    int pre[MAXN][MAXM];// 节点的前驱节点
};

// 定义坐标的结构体
struct Point {
    int x, y;
};

// 定义队列的结构体
struct Queue {
    struct Point q[MAXN * MAXM];
    int head, tail;
};

// 初始化队列
void init_queue(struct Queue *q) {
    q->head = q->tail = 0;
}

// 判断队列是否为空
int is_queue_empty(struct Queue *q) {
    return q->head == q->tail;
}

// 入队
void enqueue(struct Queue *q, struct Point p) {
    q->q[q->tail++] = p;
}

// 出队
struct Point dequeue(struct Queue *q) {
    return q->q[q->head++];
}

// 判断一个点是否合法
int is_valid(struct Maze *maze, int x, int y) {
    return x >= 0 && x < maze->n && y >= 0 && y < maze->m && maze->s[x][y] == '0';
}

// 广度优先搜索
void bfs(struct Maze *maze) {
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    struct Queue q;
    init_queue(&q);
    memset(maze->dis, INF, sizeof(maze->dis)); // 初始化距离为无穷大
    memset(maze->vis, 0, sizeof(maze->vis));   // 初始化所有节点未访问过
    maze->dis[0][0] = 0;                        // 起点到起点的距离为0
    maze->vis[0][0] = 1;                        // 标记起点为已访问
    enqueue(&q, (struct Point){0, 0});          // 将起点加入队列
    while (!is_queue_empty(&q)) {
        struct Point p = dequeue(&q);
        for (int i = 0; i < 4; i++) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (is_valid(maze, nx, ny) && !maze->vis[nx][ny]) {
                // 如果邻居节点合法且未访问过，则更新距离和前驱节点，并将其加入队列
                maze->dis[nx][ny] = maze->dis[p.x][p.y] + 1;
                maze->pre[nx][ny] = p.x * maze->m + p.y;
                maze->vis[nx][ny] = 1;
                enqueue(&q, (struct Point){nx, ny});
            }
        }
    }
}

// 输出路径
void print_path(struct Maze *maze) {
    if (maze->dis[maze->n - 1][maze->m - 1] == INF) {
        printf("NO PASS!\n");   // 没有路径
    } else {
        int len = maze->dis[maze->n - 1][maze->m - 1];
        printf("%d\n", len);     // 输出路径长度
        int cur = (maze->n - 1) * maze->m + (maze->m - 1);
        while (cur != 0) {       // 回溯路径
            int px = cur / maze->m;
            int py = cur % maze->m;
            int prex = maze->pre[px][py] / maze->m;
            int prey = maze->pre[px][py] % maze->m;
            if (prex == px + 1) printf("D");
            else if (prex == px - 1) printf("U");
            else if (prey == py + 1) printf("R");
            else printf("L");
            cur = maze->pre[px][py];
        }
        printf("\n");
    }
}

int main() {
    struct Maze maze;
    maze.n = maze.m = 0;
    while (scanf("%s", maze.s[maze.n]) != EOF) {
        maze.m = strlen(maze.s[maze.n]);
        maze.n++;
    }
    bfs(&maze);
    print_path(&maze);
    return 0;
}