Java中栈.回溯.迷宫问题求解 - 编程入门网

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]当当前判断节点为队头节点时退出.

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

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

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<T> { 　　 private LinkedList<T> storage = new LinkedList<T>(); 　　 /** 入栈 */ 　　 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(); 　　 } }

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

5.求解迷宫问题

package net.zj.maze;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!