迷宫算法问题

package cn.gao.algorithm.bean;
/*封装迷宫的基类，成员x,y分别代表第一维，第二维坐标。（当然这里可以做的灵活一点，就是设计可扩展的维数）*/
public class IndexBean {
     private int x;
     private int y;
	public IndexBean(int x, int y) {
		super();
		this.x = x;
		this.y = 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;
	}
	@Override
	public int hashCode() {
		final int PRIME = 31;
		int result = 1;
		result = PRIME * result + x;
		result = PRIME * result + y;
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		final IndexBean other = (IndexBean) obj;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "IndexBean:x="+x+" y="+y;
	}
	

    
}



package cn.gao.algorithm.model;
import cn.gao.algorithm.bean.IndexBean;

/*设计一个栈，具有基本的先进后出的栈特性*/
public class StackForTest<T> implements Cloneable{

	/**
	 * @param args
	 */
	
	private Object a[];/*栈对应的原生数组*/
	private int index;/*栈的当前索引*/
	private int max;/*栈容量*/
	
	public StackForTest(int max) {/*构造函数初始化*/
		super();
		this.max = max;
		a=new Object[max];
		index=-1;
	}
	public boolean isFull()/*判断栈是否满*/
	{
		if(index>=max-1)
		{
			return true;
		}
		return false;
	}
	public boolean isNull()/*判断栈是否空*/
	{
		if(index<=-1)
		{
			return true;
		}
		return false;
	}
	@SuppressWarnings("unchecked")
	public T get()/*出栈---获取栈中元素*/
	{
		if(!isNull())
		{
			return (T)a[index--];
		}
		return null;
	}
	public void add(T tb)/*入栈--插入栈中元素*/
	{
		if(!isFull())
		{
			a[++index]=tb;	
		}
	}
	public void remove()/*/*出栈---移除栈中元素*/
	{
		if(!isNull())
		{
			index--;
		}
	}
	public void printAll()/*自底向上遍历栈中所有元素*/
	{
	   for(int i=0;i<=index;i++)
	   {
		   System.out.println(a[i]);
	   }
	}
	public void clear()/*清空栈*/
	{
		for(int i=0;i<max;i++)
		{
			a[i]=null;
		}
		index=-1;
	}
	public int getLength()/*获取栈长度（元素个数）*/
	{
	   	return index+1;
	}
    
	@SuppressWarnings("unchecked")
	@Override
	public Object clone() throws CloneNotSupportedException {
		// TODO Auto-generated method stub
		StackForTest stackClone=new StackForTest(this.max);
		for(int i=0;i<=this.index;i++)
		{
			stackClone.add(this.a[i]);
		}
		return stackClone;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StackForTest<IndexBean> stack =new StackForTest<IndexBean>(3);
		stack.add(new IndexBean(1,2));
		stack.add(new IndexBean(2,3));
		stack.add(new IndexBean(3,4));
		System.out.println(stack.get());
		System.out.println(stack.get());
		System.out.println(stack.get());
		stack.printAll();
		System.out.println();
		stack.clear();
		stack.printAll();
	

	}

}



package cn.gao.algorithm2.service;
import cn.gao.algorithm.bean.IndexBean;
import cn.gao.algorithm.model.StackForTest;
/**
 * @param args
 * 迷宫问题：给定迷宫数组（0表示通路，1表示墙壁），从入口（startX,startY）开始，寻找到出口（endX,endY）的路径。
 * 打印所有的路径组合，并求出最短路径
 */
public class Test10 {
	public int a[][];/*迷宫数组 0表示通路，1表示墙壁*/
	public int m,n;/*迷宫数组的第一维，第二维*/
	public int flag[][];/*访问标志，0表示未访问，1表示访问过*/
	public StackForTest stack;/*逻辑栈*/
    public int startX,startY,endX,endY;/*迷宫入口和出口*/
    public StackForTest bestStack;/*保存最短路径栈*/
    public int stackLength;/*保存每次成功路径的栈长度，便于计算最短的*/
    public int count;/*统计路径个数*/
	public Test10(int[][] a) {
		super();
		this.a = a;
		m=a.length;
		n=a[0].length;
		flag=new int[m][n];
		for(int i=0;i<m;i++)/*初始化状态数组*/
		{
			for(int j=0;j<n;j++)
			{
				flag[i][j]=0;
			}
		}
		stack=new StackForTest(m*n);/*初始化栈，程序中的路径栈不可能超过迷宫数组的元素个数*/
		stackLength=0;
		count=0;
	}

	public void setEndX(int endX) {
		this.endX = endX;
	}

	public void setEndY(int endY) {
		this.endY = endY;
	}

	public void setStartX(int startX) {
		this.startX = startX;
	}
	public void setStartY(int startY) {
		this.startY = startY;
	}

	@SuppressWarnings("unchecked")
	public void findPath(int x,int y)/*从任意点(x,y)寻找最终路径endX,endY*/
    {
    	if(x<0||x>m-1||y<0||y>n-1||flag[x][y]==1)
    	{
    		return ;
    	}
    	if(x==endX&&y==endY)
    	{ 		
     		count++;
    		System.out.println("第"+count+"次路径");
    		stack.add(new IndexBean(x,y)); 
    		stack.printAll();
    		System.out.println("\n\n");
    		if(count==1)
    		{
    			stackLength=stack.getLength();
    		}
    		if(stackLength>=stack.getLength())/*判断当前获得的路径栈长度是否小于历史最小路径栈长度*/
    		{
    			stackLength=stack.getLength();
    			try {
					bestStack=(StackForTest)stack.clone();
				} catch (CloneNotSupportedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
    		}
    		stack.remove();
    		return ;
    	}
    	if(flag[x][y]==0)/*对于未访问的‘墙’，都将其访问标志直接只已访问，且返回false*/
    	{
    		if(a[x][y]==1)
    		{
    			flag[x][y]=1;
    			return ;
    		}
    		
    	}
    	/*下面主要对未访问过的且坐标为‘通道’的路径点进行递归处理*/
    	stack.add(new IndexBean(x,y)); /*入栈当前数据*/
    	flag[x][y]=1;/*置当前访问标志*/
    	findPath(x,y-1);/*左*/
    	findPath(x,y+1);/*右*/
    	findPath(x-1,y);/*上*/
    	findPath(x+1,y);/*下*/
    	stack.remove();/*对于该元素上下左右都走不通，此元素出栈*/
    }
	public void find()
	{
		findPath(startX,startY);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[][]={
				{1,1,1,1,1,1,1,1,1},
				{1,0,0,0,1,0,0,0,1},
				{1,0,1,0,0,0,1,0,1},
				{1,0,0,1,1,1,1,0,1},
				{1,1,0,0,1,0,1,0,1},
				{1,1,1,0,0,0,0,0,1},
				{1,1,1,1,1,1,1,1,1},
				
		};
		Test10 t=new Test10(a);
		t.setStartX(1);
		t.setStartY(1);
		t.setEndX(5);
		t.setEndY(7);
		t.find();
		System.out.println("总共有"+t.count+"种路径法,最短路径如下:");
		t.bestStack.printAll();
         
	}

}