public class Maze {
	public static void main(String[] args) {
		maze();
	}
	//迷宮回溯問(wèn)題
	public static void maze() {
		//創(chuàng)建二維數(shù)組模擬迷宮
		//使用1表示墻，0表示路
		int[][] map = new int[][]{
				{1, 1, 1, 1, 1, 1, 1},
				{1, 0, 0, 0, 0, 0, 1},
				{1, 0, 1, 0, 0, 0, 1},
				{1, 0, 1, 0, 1, 1, 1},
				{1, 1, 0, 0, 0, 0, 1},
				{1, 0, 1, 1, 0, 1, 1},
				{1, 0, 0, 0, 0, 0, 1},
				{1, 1, 1, 1, 1, 1, 1}
		};
		//輸出地圖
		System.out.println("迷宮：");
		for (int[] row : map) {
			for (int i : row) {
				System.out.printf("%d\t", i);
			}
			System.out.println();
		}
		System.out.println("尋路結(jié)果：");
		//開始尋路
		setWay(map, 1, 1);
		//輸出地圖
		for (int[] row : map) {
			for (int i : row) {
				System.out.printf("%d\t", i);
			}
			System.out.println("");
		}
 
	}
 
	//傳入地圖map
	//傳入開始位置(i, j)
	//如果能到達(dá)右下角(6, 5)，則說(shuō)明找到通路
	//0表示未走過(guò)，1表示墻，2表示可以走的通路，3表示已經(jīng)走過(guò)，但是走不通
	//確定方向策略：下 -> 右 -> 上 -> 左
	//若該點(diǎn)走不通，則回溯
	public static boolean setWay(int[][] map, int i, int j) {
		if (map[6][5] == 2) {
			//通路已經(jīng)找到
			return true;
		} else {
			if (map[i][j] == 0) {
				//如果當(dāng)前點(diǎn)沒(méi)有走過(guò)
				map[i][j] = 2;    //假定該點(diǎn)可以走通
				if (setWay(map, i + 1, j)) {
					//向下走
					return true;
				} else if (setWay(map, i, j + 1)) {
					//向右走
					return true;
				} else if (setWay(map, i - 1, j)) {
					//向上走
					return true;
				} else if (setWay(map, i, j - 1)) {
					//向左走
					return true;
				} else {
					//該點(diǎn)走不通
					map[i][j] = 3;
					return false;
				}
			} else {
				//如果map[i][j] != 0
				//可能是1、2、3
				return false;
			}
		}
	}
}

迷宮：
1	1	1	1	1	1	1	
1	0	0	0	0	0	1	
1	0	1	0	0	0	1	
1	0	1	0	1	1	1	
1	1	0	0	0	0	1	
1	0	1	1	0	1	1	
1	0	0	0	0	0	1	
1	1	1	1	1	1	1	
尋路結(jié)果：
1	1	1	1	1	1	1	
1	2	2	2	0	0	1	
1	3	1	2	0	0	1	
1	3	1	2	1	1	1	
1	1	0	2	2	0	1	
1	0	1	1	2	1	1	
1	0	0	0	2	2	1	
1	1	1	1	1	1	1