Java中栈.回溯.迷宫问题求解

考虑使用一个二维数组表示迷宫.所有的通路用0表示,墙用1表示,出口用9表示,入口用6表 示,已经过点用3表示.输出走出迷宫的过程.

从这个问题的求解过程中可以简单总结出两个算法,一是探路过程,二是输出路线.

1.探路过程

探路过程算法可归纳为:

[1]从入口位置开始,检查东西南北四个方向上的通路,如果发现出口则成功退出,否则将所 有通路坐标压入栈;

[2]从栈中取出一个坐标,将其标记为当前位置(标记数字3),再次判断通路情况;

[3]如此进行,直到发现出口则成功退出,若栈空而且未发现出口,则失败退出.

这里使用到的回溯过程可描述为:

每到达一点时,会将所有可能的通路坐标(标记数字0的节点)压入栈.所以当到达一点,而不 存在可能的通路时,自然没有相应的坐标压入栈,而此时便从栈中取出上一个点所压入的可能 的一个通路坐标,并继续作通路判断,这便是一个回溯的过程.

2.输出某一较短路线

将所有在探路过程中经过的点(标记数字3的节点)按实际探路路线存入队列,对头为入口, 队尾为出口.这些点可能存在绕路的情况,所以可用下面的算法输出某一较短路线.

[1]将队尾(出口)节点设置为当前判断节点;

[2]从当前判断节点(x,y)的前驱节点开始,向前遍历队列,如果发现相邻节点(其坐标可以 为(x+1,y),(x-1,y),(x,y+1),(x,y-1)之一),则删除该相临节点至当前判断节点的前驱节点之 间的所有节点;

[3]将该相临节点设置为当前判断节点,继续判断相临节点;

[4]当当前判断节点为队头节点时退出.

该算法所得到的路线不一定是最短路线,想得到最短路线,可考虑使用树结构将所有由出口 至入口的路线保留为一子树,树高最短的子树即为最短路线.但此算法可保证所得路线不会存 在绕路情况.