Status Pass(MazeType MyMaze, PosType CurPos);
void FootPrint(MazeType &MyMaze, PosType CurPos);
void MarkPrint(MazeType &MyMaze, PosType CurPos);
PosType NextPos(PosType CurPos, int Dir);

Status MazePath(MazeType &maze, PosType start, PosType end) {  
  // 算法3.3
  // 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中
  // （從棧底到棧頂），并返回TRUE；否則返回FALSE
  Stack S;
  PosType curpos;
  int curstep;
  SElemType e;

  InitStack(S);
  curpos = start;  // 設定"當前位置"為"入口位置"
  curstep = 1;     // 探索第一步
  do {
    if (Pass(maze,curpos)) {  // 當前位置可通過，即是未曾走到過的通道塊
      FootPrint(maze,curpos); // 留下足跡
      e.di =1;
      e.ord = curstep;
      e.seat= curpos;
      Push(S,e);              // 加入路徑
      if (curpos.r == end.r && curpos.c==end.c)  
        return (TRUE);        // 到達終點（出口）
      curpos = NextPos(curpos, 1);        // 下一位置是當前位置的東鄰
      curstep++;                          // 探索下一步
    } else {  // 當前位置不能通過
      if (!StackEmpty(S)) {
        Pop(S,e);
        while (e.di==4 && !StackEmpty(S)) {
          MarkPrint(maze,e.seat);  
          Pop(S,e);    // 留下不能通過的標記，并退回一步
        } // while
        if (e.di<4) {
          e.di++;
          Push(S, e);  // 換下一個方向探索
          curpos = NextPos(e.seat, e.di); // 當前位置設為新方向的相鄰塊
        } // if
      } // if
    } // else
  } while (!StackEmpty(S) );
  return FALSE;
} // MazePath

Status Pass( MazeType MyMaze,PosType CurPos) {
  if (MyMaze.arr[CurPos.r][CurPos.c]==' ')
    return 1;     // 如果當前位置是可以通過，返回1
  else return 0;  // 其它情況返回0
}

void FootPrint(MazeType &MyMaze,PosType CurPos) {
  MyMaze.arr[CurPos.r][CurPos.c]='*';
}

void MarkPrint(MazeType &MyMaze,PosType CurPos) {
  MyMaze.arr[CurPos.r][CurPos.c]='!';
}

PosType NextPos(PosType CurPos, int Dir) {
  PosType ReturnPos; 
  switch (Dir) {
    case 1:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c+1;
        break;
    case 2:
        ReturnPos.r=CurPos.r+1;
        ReturnPos.c=CurPos.c;
        break;
    case 3:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c-1;
        break;
    case 4:
        ReturnPos.r=CurPos.r-1;
        ReturnPos.c=CurPos.c;
        break;
  }
  return ReturnPos;
}