0001 // 迷宫寻径算法:在格单元s至t之间规划一条通路(如果的确存在) 0002 bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t ) { 0003 if ( ( AVAILABLE != s->status ) || ( AVAILABLE != t->status ) ) return false; //退化情况 0004 Stack<Cell*> path; //用栈记录通路(Theseus的线绳) 0005 s->incoming = UNKNOWN; s->status = ROUTE; path.push ( s ); //起点 0006 do { //从起点出发不断试探、回溯,直到抵达终点,或者穷尽所有可能 0007 Cell* c = path.top(); //检查当前位置(栈顶) 0008 if ( c == t ) return true; //若已抵达终点,则找到了一条通路;否则,沿尚未试探的方向继续试探 0009 while ( NO_WAY > ( c->outgoing = nextESWN ( c->outgoing ) ) ) //逐一检查所有方向 0010 if ( AVAILABLE == neighbor ( c )->status ) break; //试图找到尚未试探的方向 0011 if ( NO_WAY <= c->outgoing ) //若所有方向都已尝试过 0012 { c->status = BACKTRACKED; c = path.pop(); }//则向后回溯一步 0013 else //否则,向前试探一步 0014 { path.push ( c = advance ( c ) ); c->outgoing = UNKNOWN; c->status = ROUTE; } 0015 } while ( !path.empty() ); 0016 return false; 0017 }