用c语言编写程序,要求输入一个由0和1组成的迷宫规模可达99*98等,要求找到通关的最优路径,并输出路径

这道题是一个典型的图论问题，可以使用广度优先搜索（BFS）或者Dijkstra算法来解决。这里以BFS为例。

首先，我们需要定义一个结构体表示迷宫中的一个点，包括该点的坐标和是否可通行的信息。同时，我们需要定义一个队列（可以使用数组模拟）来存储待搜索的点。

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

#define MAX_ROW 99
#define MAX_COL 98

struct point {
    int x, y;
};

struct queue {
    struct point data[MAX_ROW * MAX_COL];
    int head, tail;
};

struct point predecessor[MAX_ROW][MAX_COL];
bool maze[MAX_ROW][MAX_COL] = {0};

void bfs(struct point start, struct point end);
void enqueue(struct queue *q, struct point p);
struct point dequeue(struct queue *q);
bool is_empty(struct queue *q);
void read_maze(bool maze[][MAX_COL]);
void print_maze(bool maze[][MAX_COL]);
void print_path(struct point start, struct point end);

int main(void) {
    struct point start = {0, 0}, end;
    printf("请输入迷宫：\n");
    read_maze(maze);
    printf("请输入终点坐标(x, y)：");
    scanf("%d%d", &end.x, &end.y);
    bfs(start, end);
    print_path(start, end);
    return 0;
}

void bfs(struct point start, struct point end) {
    struct queue q = {{0}, 0, 0};
    struct point p = {start.x, start.y};
    enqueue(&q, p);
    while (!is_empty(&q)) {
        p = dequeue(&q);
        if (p.x == end.x && p.y == end.y) break;
        if (p.x - 1 >= 0 && maze[p.x - 1][p.y]) {  // 上
            struct point next = {p.x - 1, p.y};
            enqueue(&q, next);
            maze[next.x][next.y] = false;
            predecessor[next.x][next.y] = p;
        }
        if (p.y + 1 <= MAX_COL - 1 && maze[p.x][p.y + 1]) {  // 右
            struct point next = {p.x, p.y + 1};
            enqueue(&q, next);
            maze[next.x][next.y] = false;
            predecessor[next.x][next.y] = p;
        }
        if (p.x + 1 <= MAX_ROW - 1 && maze[p.x + 1][p.y]) {  // 下
            struct point next = {p.x + 1, p.y};
            enqueue(&q, next);
            maze[next.x][next.y] = false;
            predecessor[next.x][next.y] = p;
        }
        if (p.y - 1 >= 0 && maze[p.x][p.y - 1]) {  // 左
            struct point next = {p.x, p.y - 1};
            enqueue(&q, next);
            maze[next.x][next.y] = false;
            predecessor[next.x][next.y] = p;
        }
    }
}

void enqueue(struct queue *q, struct point p) {
    q->data[q->tail++] = p;
}

struct point dequeue(struct queue *q) {
    return q->data[q->head++];
}

bool is_empty(struct queue *q) {
    return q->head == q->tail;
}

void read_maze(bool maze[][MAX_COL]) {
    for (int i = 0; i < MAX_ROW; ++i) {
        for (int j = 0; j < MAX_COL; ++j) {
            scanf("%d", &maze[i][j]);
        }
    }
}

void print_maze(bool maze[][MAX_COL]) {
    for (int i = 0; i < MAX_ROW; ++i) {
        for (int j = 0; j < MAX_COL; ++j) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
}

void print_path(struct point start, struct point end) {
    struct point path[MAX_ROW * MAX_COL] = {{0, 0}};
    int count = 0;
    struct point p = {end.x, end.y};
    while (p.x != start.x || p.y != start.y) {
        path[count++] = p;
        p = predecessor[p.x][p.y];
    }
    path[count++] = p;
    printf("最短路径如下：\n");
    for (int i = count - 1; i >= 0; --i) {
        printf("(%d, %d)\n", path[i].x, path[i].y);
    }
}

在这个代码中，我们使用了一个二维数组`maze`来表示迷宫，其中`maze[i][j]`表示(i,j)这个点是否可通行。我们还定义了一个二维数组`predecessor`用来记录每个点的前驱节点，以便输出最短路径。

在`bfs`函数中，我们使用一个队列来存储待搜索的点，先将起点入队。然后每次取出队头元素，判断其上下左右四个方向是否可通行，如果可通行，则将新的点加入队列，并将其前驱节点设置为当前点。当队列为空或者找到终点时，搜索结束。

最后，我们可以使用`print_path`函数来输出最短路径，具体步骤是：从终点开始，沿着每个点的前驱节点一直走到起点，将路径上的点按顺序存入一个数组中，最后按照顺序输出即可。