raw.doc
口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障
碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可
通。
2、如果在某个位置上四个方向都走不通的话，就退回到前一个位
置，换一个方向再试，如果这个位置已经没有方向可试了就再退一
步，如果所有已经走过的位置的四个方向都试探过了，一直退到起
始点都没有走通，那就说明这个迷宫根本不通。
3、所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不
能重复走第二次"，它包括"曾经走过而没有走通的路"。
显然为了保证在任何位置上都能沿原路退回，需要用一个"后进
先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口
之后，栈中保存的正是一条从入口到出口的路径。
4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探
索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，
然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个
方块均“不可通”，则应从“当前路径”上删除该通道块。
所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、
北）上相邻的方块。假设以栈 S 记录“当前路径”，则栈顶中存放的
是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。
5、找通路的程序的关键部分可以表示如下：
do{
评论5
最新资源