Question

求Java关于迷宫的算法（用栈实现）

怎么找出下面迷宫的路径，并且将路径打印出来。
用栈实现
W代表墙，S开始点，F是终点，O是可以走得路
不要网上的代码。
我已经将下面的图存到char mazemap[12][58]中了

谢谢各位了

Answer 1

package com.Albert.LabyringhStack;

public class Point {
	int x;
	int y;
	int direction;   //direction指向此点附近的一个点 应该有四个 编号为1 2 3 4
	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;
	}
	
	public int getDirection() {
		return direction;
	}
	public void setDirection(int direction) {
		this.direction = direction;
	}
	public void addDirection(){
		this.direction++;
		
	}
	public Point() {
	}
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
		this.direction = 1;
	}
	public Point(int x, int y, int direction) {
		super();
		this.x = x;
		this.y = y;
		this.direction = direction;
	}
	
}

package com.Albert.LabyringhStack;

import java.util.*;

public class LabyringhStack {

	public Point S;
	public Point F;
	char[][] mazemap;
	Stack<Point> path;
	
	public LabyringhStack() {
	}
	public LabyringhStack(char[][] ma) {        //初始化 存入数组
		this.mazemap = new char[ma.length][ma[0].length];
		for(int i=0;i<ma.length;i++){
			for(int j=0;j<ma[0].length;j++){   //mazemap[0]必须有元素 不可为空
				this.mazemap[i][j] = ma[i][j];
			}
		}
		S = returnPlace('S');
		F = returnPlace('F');
	}
	public Point returnPlace(char s){      //返回数组中字符的位置
		Point point = new Point();
		for(int i=0;i<this.mazemap.length;i++){
			for(int j=0;j<this.mazemap[0].length;j++){   //mazemap[0]必须有元素 不可为空
				if(this.mazemap[i][j]==s)
				{   point.setX(i);
					point.setY(j);
					point.setDirection(1);
				}
				}
		}
		return point;
	}
	public char returnChar(Point point){
		if(point.getX()>=0&&point.getY()>=0)
		  return this.mazemap[point.getX()][point.getY()];
		else
		  return '#';
	}
	public void replacePlace(Point point, char s){  //更改特定位置处的字符
		mazemap[point.getX()][point.getY()] = s;
	}
	public void printPath(){
		Stack<Point> tempPath = new Stack<Point>();
		while(!path.empty()){                                      //对栈进行反序
			tempPath.push(path.pop());
		}
		while(!tempPath.empty()){
			System.out.print("("+tempPath.peek().getX()+","+tempPath.pop().getY()+")");
		}
	}
	public boolean getPath(){                   //取得路径的算法  如果有路径就返回真
		path = new Stack<Point>();
		S.setDirection(1);
		path.push(S);
		replacePlace(S, 'X');
		while(!path.empty()){
			Point nowPoint = path.peek();    //取得当前位置
			if(nowPoint.getX()==F.getX()&&nowPoint.getY()==F.getY()){
				//printPath();
				return true;
			}
			Point temp = new Point();        //存放下一个可走的位置
			int find = 0;                    //标志   是否可向下走
			while(nowPoint.getDirection()<5&&find==0){
				switch(nowPoint.getDirection()){
				case 1:temp = new Point(nowPoint.getX(),nowPoint.getY()-1,1); break;  //取得当前位置左边的位置  
				case 2:temp = new Point(nowPoint.getX()+1,nowPoint.getY(),1); break;//取得当前位置下边的位置  
				case 3:temp = new Point(nowPoint.getX(),nowPoint.getY()+1,1); break;//取得当前位置右边的位置  
				case 4:temp = new Point(nowPoint.getX()-1,nowPoint.getY(),1); break;//取得当前位置上边的位置 
				}
				nowPoint.addDirection();                    //指向下一个需要验证的点
				if(returnChar(temp)=='O'||returnChar(temp)=='F') find = 1;    //如果能向下走则置为1
			}
				if(find==1){                                    //如果可走就进栈
					replacePlace(temp, 'X');           //设置成X 防止回走
//					printArr();
					path.push(temp);
				}else{                                         //如果不可走就退栈
					replacePlace(nowPoint, 'O');     
					path.pop();
				}
			}	
		return false;
	}
	public void printArr(){
		for(int i=0;i<mazemap.length;i++){
			for(int j=0;j<mazemap[0].length;j++){   //mazemap[0]必须有元素 不可为空
				System.out.print(mazemap[i][j]);
			}
			System.out.println();
		}	
		System.out.println();
	}

}

package com.Albert.LabyringhStack;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[][] mazemap = {
				{'M','M','M','M','M','M','M','M'},
				{'M','S','O','O','M','M','M','M'},
				{'M','M','M','O','M','M','M','M'},
				{'M','M','O','O','O','O','M','M'},
				{'M','M','M','M','M','F','M','M'},
				{'M','M','M','M','M','M','M','M'},
				{'M','M','M','M','M','M','M','M'}
		};
	  LabyringhStack solution = new LabyringhStack(mazemap);
	  if(solution.getPath()){
		  System.out.print("迷宫路径如下：");
		  solution.printPath();
	  }
	  else {
		  System.out.println("没有可走的路");
	}
    }
}