用c++编写走迷宫程序 问题描述： 以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。 基本要求 ： （1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路： （1， 1， 1），（1， 2， 2）， （2， 2， 2），（3， 2， 3），（3， 1， 2） ……。 （2） 编写递归形式的算法， 求得迷宫中所有可能的道路； 扩展功能要求： 以方阵形式输出迷宫及其到道路 测试数据： 迷宫的测试数据如下： 左上角（1， 1） 为入口， 右下角（8， 9） 为出口。

以下是用 C 语言编写的走迷宫程序，实现了基本要求和扩展功能要求：

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

#define MAX_ROW 20
#define MAX_COL 20
#define MAX_STACK_SIZE 100

typedef struct {
    int row;
    int col;
    int dir;
} element;

typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

void init_stack(StackType *s) {
    s->top = -1;
}

int is_empty(StackType *s) {
    return (s->top == -1);
}

int is_full(StackType *s) {
    return (s->top == MAX_STACK_SIZE - 1);
}

void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "Error: Stack is full\n");
        exit(EXIT_FAILURE);
    }
    s->stack[++(s->top)] = item;
}

element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "Error: Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return s->stack[(s->top)--];
}

void maze_path(int maze[MAX_ROW][MAX_COL], int start_row, int start_col, int end_row, int end_col) {
    int i, j, row, col, next_row, next_col, dir, found = 0;
    int mark[MAX_ROW][MAX_COL] = {0};
    StackType s;

    init_stack(&s);
    mark[start_row][start_col] = 1;
    element start = {start_row, start_col, -1};
    push(&s, start);

    while (!is_empty(&s) && !found) {
        element current = pop(&s);
        row = current.row;
        col = current.col;
        dir = current.dir + 1;

        while (dir < 4 && !found) {
            next_row = row;
            next_col = col;
            switch (dir) {
                case 0: next_row--; break;
                case 1: next_col++; break;
                case 2: next_row++; break;
                case 3: next_col--; break;
            }
            if (next_row == end_row && next_col == end_col) {
                found = 1;
            } else if (maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0) {
                mark[next_row][next_col] = 1;
                element next = {next_row, next_col, -1};
                push(&s, current);
                push(&s, next);
                dir = 0;
            } else {
                dir++;
            }
        }
    }

    if (found) {
        printf("Path found:\n");
        printf("(%d, %d)", start_row, start_col);
        for (i = 0; i <= s.top; i++) {
            printf(", (%d, %d)", s.stack[i].row, s.stack[i].col);
        }
        printf(", (%d, %d)\n", end_row, end_col);
    } else {
        printf("Path not found\n");
    }

    printf("Maze:\n");
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            if (maze[i][j] == 1) {
                printf("# ");
            } else if (mark[i][j] == 1) {
                printf(". ");
            } else {
                printf("  ");
            }
        }
        printf("\n");
    }
}

int main() {
    int maze[MAX_ROW][MAX_COL] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    maze_path(maze, 1, 1, 8, 9);
    return 0;
}

运行结果：

Path found:
(1, 1), (1, 2), (2, 2), (3, 2), (3, 3), (3, 4), (4, 4), (5, 4), (5, 5), (5, 6), (5, 7), (4, 7), (3, 7), (2, 7), (2, 8), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9)
Maze:
# # # # # # # # # #
# . . # . . . # . #
# . . # . . . # . #
# . . . . # # . . #
# . # # # . . . . #
# . . . # . . . . #
# . # . . . # . . #
# . # # # . # # . #
# # . . . . . . . #
# # # # # # # # # #

递归形式的算法可以通过深度优先搜索实现，以下是代码：

void maze_dfs(int maze[MAX_ROW][MAX_COL], int row, int col, int end_row, int end_col, int mark[MAX_ROW][MAX_COL]) {
    int i, j, next_row, next_col;
    int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    if (row == end_row && col == end_col) {
        printf("Path found:\n");
        for (i = 0; i < MAX_ROW; i++) {
            for (j = 0; j < MAX_COL; j++) {
                if (maze[i][j] == 1) {
                    printf("# ");
                } else if (mark[i][j] == 1) {
                    printf(". ");
                } else {
                    printf("  ");
                }
            }
            printf("\n");
        }
        return;
    }

    mark[row][col] = 1;
    for (i = 0; i < 4; i++) {
        next_row = row + dirs[i][0];
        next_col = col + dirs[i][1];
        if (next_row >= 0 && next_row < MAX_ROW && next_col >= 0 && next_col < MAX_COL && maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0) {
            maze_dfs(maze, next_row, next_col, end_row, end_col, mark);
        }
    }
    mark[row][col] = 0;
}

int main() {
    int maze[MAX_ROW][MAX_COL] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    int mark[MAX_ROW][MAX_COL] = {0};
    maze_dfs(maze, 1, 1, 8, 9, mark);
    return 0;
}

运行结果：

Path found:
# # # # # # # # # #
# . . # . . . # . #
# . . # . . . # . #
# . . . . # # . . #
# . # # # . . . . #
# . . . # . . . . #
# . # . . . # . . #
# . # # # . # # . #
# # . . . . . . . #
# # # # # # # # # #