程序运行结果：

C语言迷宫求解——栈的应用 - 图1

算法思想及程序实现：

  1. 求迷宫路径算法的基本思想：若当前位置“可通”，则纳入路径，继续前进;

若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。

  1. 定义相关结构体：
  1.  //迷宫中的坐标位置
  2. typedef struct {
  3.     int x;//行号
  4.     int y;//列号
  5. } PosType;
  7. //栈的元素类型
  8. typedef struct {
  9.     PosType seat;//通道块在迷宫中的“坐标位置”
  10.     int direction;//从此通道块走向下一通道块的方向,di=1,2,3,4分别表示东，南，西，北
  11. } SElemType;
  13. typedef struct SqStack {
  14.     SElemType data[MAXSIZE];
  15.     int top;//指向栈顶元素
  16. } SqStack;
  1. 通过二维数组定义迷宫，并设置起点和终点坐标，（’ ‘表示通道块，’#’表示墙壁，在后面的执行过程中，迷宫的元素可能变成’*’表示路径，’@’表示曾经走过但是无法到达出口）：
  1. //定义迷宫，' '表示通道块，'#'表示墙壁，在后面的执行过程中，迷宫的元素可能变成'*'表示路径，'@'表示曾经走过但是无法到达出口
  2. static char maze[mazeRowNum][mazeRowNum] = {
  3.     {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
  4.     {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
  5.     {'#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#'},
  6.     {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
  7.     {'#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#'},
  8.     {'#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', '#'},
  9.     {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
  10.     {'#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#'},
  11.     {'#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
  12.     {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
  13. };
  15. PosType start = {1, 1};//设置迷宫起点
  16. PosType end = {8, 8};//设置迷宫终点
  1. 对曾经走过的通道块留下痕迹，以防止所求路径不是简单路径：
  1. void footPrint(PosType curpos) {
  2.     maze[curpos.x][curpos.y] = '*';//表示到达了该通道块
  3. }
  1. 曾走过的通道块但是无法到达出口，是“不通的”路，标记以免陷入“死胡同”：
  1. void markPrint(PosType curpos) {
  2.     maze[curpos.x][curpos.y] = '@';//表示该通道块虽然不是墙壁，但是它仍然不通
  3. }
  1. 定义函数实现从当前位置“行走”到下一个位置：
  1. PosType nextPos(PosType curpos, int direction) {
  2.     switch(direction) {
  3.         case 1:
  4.             curpos.y++;
  5.             break;//向东走，行号不变，列号加1
  6.         case 2:
  7.             curpos.x++;
  8.             break;//向南走，行号加1，列号不变
  9.         case 3:
  10.             curpos.y--;
  11.             break;//向西走，行号不变，列号减1
  12.         case 4:
  13.             curpos.x--;
  14.             break;//向北走，行号减1，列号不变
  15.     }
  16.     return curpos;
  17. }
  1. 判断当前位置是否可通,即为’ ‘，而不是’#’、’*’（已走过）、’@’（已走过但不通）：
  1. bool pass(PosType curpos) {
  2.     if(maze[curpos.x][curpos.y] == ' ')
  3.         return true;
  4.     else
  5.         return false;
  6. }
  1. 若迷宫中存在从入口start到出口end的通道，则求得一条路径存放在栈中（从栈底到栈顶），并返回TRUE,否则返回FALSE：
  1. bool mazePath(PosType start, PosType end) {
  2.     SqStack s;
  3.     initStack(s);
  4.     PosType curpos = start;//设定当前位置为“入口”位置
  5.     //int curstep = 0;  //探索的第一步，用于表示路径序号
  6.     do {
  7.         if(pass(curpos)) { //当前路径可通（是未曾到达过的通道块）
  8.             footPrint(curpos);//留下"到此一游"的标记，为了求得的路径是简单路径
  9.             //SElemType e = {curpos, 1};
  10.             SElemType e;
  11.             e.seat = curpos;
  12.             e.direction = 1;
  13.             push(s, e);  //加入路径
  14.             if(curpos.x == end.x && curpos.y == end.y)  //到达出口
  15.                 return true;
  16.             curpos = nextPos(curpos, 1);//下一位置是当前位置的东边
  17.             //curstep++;   //探索下一步
  18.         } else { //当前位置不能通过，则栈顶元素出栈，因为栈顶位置是当前位置的“来向”通道块，即当前位置的前一个位置
  19.             SElemType e;
  20.             pop(s, e);
  21.             //如果弹出的栈顶位置的四周均不可通，则继续往“来路”通道块回退
  22.             while(e.direction == 4 && !isEmpty(s)) {
  23.                 markPrint(e.seat);//标记此通道块已经走过且不可通，标记是为了避免陷入死胡同
  24.                 pop(s, e);
  25.             }
  26.             //弹出的栈顶位置尚有其他方向的方块未探索，则切换到下一个方向的方块为当前位置
  27.             if(e.direction < 4) {
  28.                 e.direction++;
  29.                 push(s, e);
  30.                 curpos = nextPos(e.seat, e.direction);
  31.             }
  32.         }//end else
  33.     } while(!isEmpty(s));//栈不为空则循环继续
  34.     return false;
  35. }
  1. 定义函数打印迷宫：
  1. //打印迷宫
  2. void printMaze() {
  3.     for(int i = 0; i < mazeRowNum; i++) {
  4.         for(int j = 0; j < mazeColNum; j++) {
  5.             printf("%c ", maze[i][j]);
  6.         }
  7.         printf("\n");
  8.     }
  9.     printf("\n");
  10. }
  11. //仅打印迷宫中的路径
  12. void printPath() {
  13.     for(int i = 0; i < mazeRowNum; i++) {
  14.         for(int j = 0; j < mazeColNum; j++) {
  15.             if(i == 0 || j == 0 || i == mazeRowNum-1 || j == mazeColNum-1 || maze[i][j] == '*') {
  16.                 printf("%c ", maze[i][j]);
  17.             } else {
  18.                 printf("  ");
  19.             }
  20.         }
  21.         printf("\n");
  22.     }
  23.     printf("\n");
  24. }
  25. //仅打印迷宫中的路径坐标 
  26. void printPathOrder() {
  27.     for(int i = 0; i < mazeRowNum; i++) {
  28.         for(int j = 0; j < mazeColNum; j++) {
  29.             if( maze[i][j] == '*') {
  30.                 printf("(%d,%d) ", i,j);
  31.             }
  32.         }
  33.     }
  34.     printf("\n");
  35. }
  1. 主函数
  1. int main() {
  2.     printf("迷宫的初始状态：\n");
  3.     printMaze();
  4.     if(mazePath(start, end)) {
  5.         printf("存在通路！\n\n");
  6.         printf("路径坐标：\n");
  7.         printPathOrder();
  8.         printf("\n迷宫的现态：\n");
  9.         printMaze();
  10.         printf("迷宫里的路径：\n");
  11.         printPath();
  12.     } else
  13.         printf("不存在通路！\n");
  14.     return 0;
  15. }