java-小老鼠走迷宮(堆疊)－書籍分享天地

程式我放在Github:Francis-Angus/java-Algorithm (github.com)

執行結果:

實際迷宮(綠:起點、紅:終點):

下面我來分別介紹程式片段

    public static int ExitX=2;
    public static int ExitY=8;
    public static int stack[][] = new int[30][2];
    public static int top=-1; //堆疊指標
    public static int [][] MAZE= {{1,1,1,1,1,1,1,1,1,1,1,1},
								  {1,0,0,0,0,0,0,1,1,1,1,1},
								  {1,0,1,0,1,1,0,1,0,0,0,1},
								  {1,0,1,0,1,1,0,1,1,1,0,1},
								  {1,0,1,0,0,0,0,1,1,1,0,1},
								  {1,0,1,0,1,1,0,0,0,1,0,1},
								  {1,0,1,0,1,1,0,1,1,1,0,1},
								  {1,0,1,1,1,1,0,1,1,1,0,1},
								  {1,0,0,0,1,0,0,0,0,0,0,1},
								  {1,1,1,1,1,1,1,1,1,1,1,1}};

1. 0代表路、1代表牆壁、2代表走過、3代表到終點

2.這是[10][12]的陣列，前面的10是x(上下)，12是y(左右)不要搞混了，跟一般的座標軸x(左右)、y(上下)是不同的。

3.終點我設[2][8]，記得陣列是從0開始。

4.用[30][2]來記得走過的路，top為放入此陣列的數量。

5.也可以用鏈結串列來做，只不過會多很多程式碼。

int x=1,y=1;

top=0; //先存入，不然會回不到原點
stack[top][0]=x;
stack[top][1]=y;

1. x、y為初始位置。

2.把原點存入堆疊，可以看下面這張圖，範例程式沒有儲存原點(因為他不會往回走到原點)會發生什麼事?當你往回走會走不到初始點，直接把堆疊的內容變成-1報錯，如果有保護機制會變成無限回圈。

while(true)
		{
			MAZE[x][y]=2;
			if(walk(x,y)){ //新增到堆疊
				x=stack[top][0];
				y=stack[top][1];
				
				
			}else if(x==ExitX && y==ExitY) { //到終點離開
				MAZE[x][y]=3;
				break;
				
			}else //遇到死路往回退
			{
				top--;
				x=stack[top][0];
				y=stack[top][1];
			}
		}

public static boolean walk(int x,int y)
	{
		if(MAZE[x+1][y] == 0) //上
			x++;
	
		else if(MAZE[x-1][y] == 0) //下
			x--;
			
		else if(MAZE[x][y+1] == 0)  //左
			y++;
			
		else if(MAZE[x][y-1] == 0)  //右
			y--;
			
		else 
			return false;
		
		top++;
		stack[top][0]= x;
		stack[top][1]= y;
		
		return true;
	}