考虑使用一个二维数组表示迷宫.所有的通路用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]当当前判断节点为队头节点时退出.
该算法所得到的路线不一定是最短路线,想得到最短路线,可考虑使用树结构将所有由出口 至入口的路线保留为一子树,树高最短的子树即为最短路线.但此算法可保证所得路线不会存 在绕路情况.
3.表示节点坐标的类
public class MazeCell { private int x, y;//表示x轴y轴坐标 public MazeCell() { } public MazeCell(int i, int j) { x = i; y = j; } public boolean equals(Object o) { if (!(o instanceof MazeCell)) return false; MazeCell cell = (MazeCell) o; return cell.x == x && cell.y == y; } public String toString() { return x + "," + y; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; }}
4.所使用的栈数据结构
import java.util.LinkedList;public class Stack { private LinkedList sTorage = new LinkedList(); /** 入栈 */ public void push(T v) { sTorage.addFirst(v); } /** 出栈，但不删除 */ public T peek() { return sTorage.getFirst(); } /** 出栈 */ public T pop() { return sTorage.removeFirst(); } /** 栈是否为空 */ public boolean empty() { return sTorage.isEmpty(); } /** 打印栈元素 */ public String toString() { return sTorage.toString(); }}
5.求解迷宫问题
package net.zj.maze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintStream;import java.util.IteraTor;import java.util.LinkedList;import java.util.List;import java.util.ListIteraTor;public class Maze { private int rows = 0, cols = 0;// 迷宫的行数与列数 private char[][] sTore, path;// 迷宫矩阵 private MazeCell currentCell, exitCell = new MazeCell(), entryCell = new MazeCell();// 当前节点,出口节点,入口节点 private static final char EXIT = '9', ENTRY = '6', VISITED = '3';// 出口标记,入口标记,已经过节点标记 private static final char PASS = '0', WALL = '1';// 通路标记,墙标记 private Stack mazeStack = new Stack();// 探路过程所使用栈 private List currentList = new LinkedList();// 路经的路线队列 public Maze() { // 构造迷宫 int row = 0, col = 0; Stack mazeRows = new Stack(); InputStreamReader isr = new InputStreamReader(System.in); BufferedReader buffer = new BufferedReader(isr); System.out.println("Enter a rectangular maze using the following" + " characters: /n6-entry/n9-exit/n1-wall/n0-passage/n" + "Enter one line at a time; end with Ctrl-d;"); try { String str = buffer.readLine(); while (str != null) { row++; cols = str.length(); str = "1" + str + "1"; mazeRows.push(str); if (str.indexOf(EXIT) != -1 思想如钻子，必须集中在一点钻下去才有力量
