一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2.实现要求⑴实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。⑵编写递归形式的算法，求得迷宫中所有可能的通路；⑶以方阵形式输出迷宫及其通路。用c语音实现

以下是用 C 语言实现的程序，包括链表栈类型和迷宫求解程序：

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

#define MAX_ROW 20
#define MAX_COL 20

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

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

typedef struct stackNode {
    element data;
    struct stackNode *link;
} stackNode;

stackNode *top;

void push(int row, int col, int dir) {
    stackNode *temp = (stackNode *)malloc(sizeof(stackNode));
    temp->data.row = row;
    temp->data.col = col;
    temp->data.dir = dir;
    temp->link = top;
    top = temp;
}

element pop() {
    stackNode *temp = top;
    element item;
    if (temp == NULL) {
        printf("stack empty\n");
    } else {
        item = temp->data;
        top = temp->link;
        free(temp);
    }
    return item;
}

position move(position pos, int dir) {
    switch (dir) {
        case 0: pos.row -= 1; break;
        case 1: pos.col += 1; break;
        case 2: pos.row += 1; break;
        case 3: pos.col -= 1; break;
    }
    return pos;
}

void printMaze(int maze[][MAX_COL], int row, int col) {
    int i, j;
    printf("Maze:\n");
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
}

void printPath(element path[], int start, int end) {
    int i;
    printf("Path:\n");
    for (i = start; i <= end; i++) {
        printf("(%d,%d,%d) ", path[i].row, path[i].col, path[i].dir);
    }
    printf("\n");
}

void mazePath(int maze[][MAX_COL], int row, int col, int startRow, int startCol, int endRow, int endCol) {
    int i, j, dir, found = 0;
    position here;
    element exitCell, pos;
    top = NULL;
    here.row = startRow;
    here.col = startCol;
    here.dir = -1;
    push(here.row, here.col, here.dir);
    maze[startRow][startCol] = -1;
    while (top != NULL && !found) {
        pos = pop();
        here.row = pos.row;
        here.col = pos.col;
        here.dir = pos.dir + 1;
        while (here.dir < 4) {
            i = here.row;
            j = here.col;
            dir = here.dir;
            here = move(here, dir);
            if (i == endRow && j == endCol) {
                found = 1;
                exitCell.row = i;
                exitCell.col = j;
                exitCell.dir = dir;
                push(exitCell.row, exitCell.col, exitCell.dir);
                break;
            } else if (maze[here.row][here.col] == 0) {
                push(here.row, here.col, here.dir);
                maze[here.row][here.col] = -1;
                here.dir = -1;
            }
            here = move(here, 3-dir);
            here.dir++;
        }
    }
    if (found) {
        element path[MAX_ROW*MAX_COL];
        int count = 0;
        printf("Path found!\n");
        while (top != NULL) {
            path[count] = pop().data;
            count++;
        }
        printPath(path, count-1, 0);
    } else {
        printf("Path not found.\n");
    }
}

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

以上程序实现了一个以链表作存储结构的栈类型和一个求解迷宫的非递归程序。其中，`mazePath()`函数实现了根据迷宫和起点、终点坐标求解迷宫的功能，如果找到通路，则输出通路上经过的格子及方向；如果没有通路，则输出提示信息。