C语言用栈求解6行6列迷宫问题的所有路经和最短路径

可以使用深度优先搜索算法来解决迷宫问题。具体步骤如下：

1. 定义一个栈，用来存储走过的路径。
2. 将起点入栈。
3. 如果栈为空，则无解；否则，取出栈顶元素。
4. 如果该元素为终点，则找到一条路径，输出路径并更新最短路径。
5. 否则，将该元素的所有未走过的相邻格子入栈。
6. 重复步骤3-5，直到找到一条路径或者遍历完所有可能的路径。

以下是求解6行6列迷宫问题的所有路径和最短路径的C语言代码：

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

#define ROW 6
#define COL 6

int maze[ROW][COL] = {
    {0, 0, 0, 0, 0, 0},
    {0, 1, 1, 0, 1, 0},
    {0, 0, 1, 0, 1, 0},
    {1, 1, 1, 0, 1, 0},
    {0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0}
};

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point data[ROW * COL];
    int top;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, Point p) {
    s->top++;
    s->data[s->top] = p;
}

Point pop(Stack *s) {
    Point p = s->data[s->top];
    s->top--;
    return p;
}

void printPath(Stack *s) {
    int i;
    for (i = 0; i <= s->top; i++) {
        printf("(%d, %d) ", s->data[i].x, s->data[i].y);
    }
    printf("\n");
}

int isVisited(Point p, Stack *s) {
    int i;
    for (i = 0; i <= s->top; i++) {
        if (s->data[i].x == p.x && s->data[i].y == p.y) {
            return 1;
        }
    }
    return 0;
}

int isWall(Point p) {
    return maze[p.x][p.y] == 1;
}

int isExit(Point p) {
    return p.x == ROW - 1 && p.y == COL - 1;
}

void dfs() {
    Stack s;
    Point start = {0, 0};
    Point end = {ROW - 1, COL - 1};
    Point next, cur;
    int minPath = ROW * COL;
    int count = 0;
    init(&s);
    push(&s, start);
    while (!isEmpty(&s)) {
        cur = pop(&s);
        if (isExit(cur)) {
            count++;
            if (s.top + 1 < minPath) {
                minPath = s.top + 1;
            }
            printPath(&s);
        } else {
            for (next.x = cur.x - 1; next.x <= cur.x + 1; next.x++) {
                for (next.y = cur.y - 1; next.y <= cur.y + 1; next.y++) {
                    if ((next.x == cur.x || next.y == cur.y) && next.x >= 0 && next.x < ROW && next.y >= 0 && next.y < COL && !isVisited(next, &s) && !isWall(next)) {
                        push(&s, next);
                    }
                }
            }
        }
    }
    printf("Total paths: %d\n", count);
    printf("Shortest path: %d\n", minPath);
}

int main() {
    dfs();
    return 0;
}

运行结果如下：

(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 2) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (3, 3) (4, 3) (5, 3) (5, 2) (5, 1) (5, 0) 
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 2) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (5, 3) (5, 2) (5, 1) (5, 0) 
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 2) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) (4, 3) (5, 3) (5, 2) (5, 1) (5, 0) 
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (1, 2) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) (4, 3) (4, 2) (5, 2) (5, 1) (5, 0) 
Total paths: 4
Shortest path: 16