package cc;

public class MazeNode {
	private int value;//迷宮節(jié)點(diǎn)數(shù)據(jù)0或者1
	private int i;//迷宮節(jié)點(diǎn)所在的行
	private int j;//迷宮節(jié)點(diǎn)所在的列
	private boolean[] state;//當(dāng)前節(jié)點(diǎn)可走或不可走
	/*構(gòu)造*/
	public MazeNode(int value,int i,int j) {
		this.value=value;
		this.i=i;
		this.j=j;
		state=new boolean[Constant.SIZE];
	}
	
	/*get和set*/
	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public int getI() {
		return i;
	}

	public int getJ() {
		return j;
	}
	public void setState(int direction,boolean state) {
		this.state[direction]=state;
	}
	public boolean getState(int direction) {
		return state[direction];
	}
	
}

package cc;

public class Constant {
	public static final int SIZE=4;//四個(gè)方向
	public static final int EAST=0;//東
	public static final int WEAST=1;//西
	public static final int SORTH=2;//南
	public static final int NORTH=3;//北
	public static final int ABLE=0;//可走
}

package cc;

import java.util.Scanner;
import java.util.Stack;

/*
 * @author : CC
 * @data : 2020-12-14
 * */
public class Maze {
	private MazeNode[][] mazeNodes;//迷宮數(shù)組
	private int column;//列
	private int row;//行
	private Stack<MazeNode> stack;//棧
	/*構(gòu)造*/
	public Maze(int row,int column) {
		this.mazeNodes=new MazeNode[row][column];
		this.column=column;
		this.row=row;
		stack=new Stack<MazeNode>();
	}
	
	/*初始化迷宮*/
	private void initValue() {
		Scanner sc=new Scanner(System.in);
		System.out.println("請(qǐng)輸入迷宮路徑:");
		for(int i=0;i<row;i++) {
			for(int j=0;j<column;j++) {
				this.mazeNodes[i][j]=new MazeNode(sc.nextInt(),i,j);
			}
		}
		sc.close();
	}
	/*初始化迷宮節(jié)點(diǎn)的狀態(tài)*/
	private void initState() {
		for(int i=0;i<row;i++) {
			for(int j=0;j<column;j++) {
				if(mazeNodes[i][j].getValue()==Constant.ABLE) {
					//東
					if(j+1<column&&mazeNodes[i][j+1].getValue()==Constant.ABLE) {
						mazeNodes[i][j].setState(Constant.EAST,true);
					}
					//南
					if(i+1<row&&mazeNodes[i+1][j].getValue()==Constant.ABLE) {
						mazeNodes[i][j].setState(Constant.SORTH,true);
					}
					//西
					if(j-1>=0&&mazeNodes[i][j-1].getValue()==Constant.ABLE) {
						mazeNodes[i][j].setState(Constant.WEAST,true);
					}
					//北
					if(i-1>=0&&mazeNodes[i-1][j].getValue()==Constant.ABLE) {
						mazeNodes[i][j].setState(Constant.NORTH,true);
					}
				}
			}
		}
	}
	/*走迷宮*/
	public void goMaze() {
		initValue();
		initState();
		if(mazeNodes[0][0].getValue()!=Constant.ABLE) {
			//如果連起點(diǎn)都不能走的話，就表示沒(méi)有路徑
			System.out.println("沒(méi)有迷宮路徑!");
			return;
		}
		//起點(diǎn)入棧
		stack.push(mazeNodes[0][0]);
		//開始走迷宮
		while(!stack.isEmpty()) {
			MazeNode top=stack.peek();//獲取棧頂元素
			int i=top.getI();
			int j=top.getJ();
			if(i==row-1&&j==column-1) {
				//找到了終點(diǎn)
				System.out.println("找到迷宮路徑!");
				show();
				return;
			}
			//判斷棧頂元素是否是死胡同
			if(top.getState(Constant.EAST)==false&&top.getState(Constant.WEAST)==false&&top.getState(Constant.NORTH)==false&&top.getState(Constant.SORTH)==false) {
				//如果是，直接出棧
				stack.pop();
			}
			//判斷各個(gè)位置是否可走
			//由于起點(diǎn)在左上角，所以我們從東邊開始判斷
			if(top.getState(Constant.EAST)) {
				stack.push(mazeNodes[i][j+1]);//東邊入棧
				//當(dāng)前節(jié)點(diǎn)的東邊f(xié)alse
				mazeNodes[i][j].setState(Constant.EAST, false);
				//當(dāng)前節(jié)點(diǎn)的東邊節(jié)點(diǎn)的西邊f(xié)alse
				mazeNodes[i][j+1].setState(Constant.WEAST, false);
			}
			//南
			if(top.getState(Constant.SORTH)) {
				stack.push(mazeNodes[i+1][j]);//南邊入棧
				
				mazeNodes[i][j].setState(Constant.SORTH, false);
				
				mazeNodes[i+1][j].setState(Constant.NORTH, false);
			}
			//西
			if(top.getState(Constant.WEAST)) {
				stack.push(mazeNodes[i][j-1]);//西邊入棧
				
				mazeNodes[i][j].setState(Constant.WEAST, false);
				
				mazeNodes[i][j-1].setState(Constant.EAST, false);
			}
			//北
			if(top.getState(Constant.NORTH)) {
				stack.push(mazeNodes[i-1][j]);//北邊入棧
				
				mazeNodes[i][j].setState(Constant.NORTH, false);
				
				mazeNodes[i-1][j].setState(Constant.SORTH, false);
			}
		}
		System.out.println("此迷宮無(wú)解!");
	}
	/*輸出路徑*/
	private void show(){
  while (!stack.isEmpty()) {
   MazeNode top = stack.peek();// 獲取棧頂元素
   top.setValue(2);
   stack.pop();// 出棧操作
  }
   System.out.println("所找到的路徑為值2的坐標(biāo)：");
  for(int i = 0;i<row;i++){
   for(int j = 0;j<column;j++){
    System.out.print(mazeNodes[i][j].getValue()+" ");
   }
   System.out.println();
  }
 }

}

package cc;

public class Test {
	public static void main(String[] args) {
		Maze t1=new Maze(4,5);
		t1.goMaze();
	}
}