Java數(shù)據(jù)結(jié)構(gòu) 遞歸之迷宮回溯案例講解

更新時間：2021年08月03日 09:19:17 作者：去吧貓頭夜鷹

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)遞歸之迷宮回溯案例講解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

問題介紹：

用二維數(shù)組表示一個迷宮，設(shè)置迷宮起點和終點，輸出迷宮中的一條通路

實現(xiàn)思路：

二維數(shù)組表示迷宮：

0表示路且未走過、1表示墻、2表示通路，3表示已經(jīng)走過但走不通

設(shè)置尋路方法setWay，傳入地圖和坐標(biāo)參數(shù)

默認(rèn)方向策略：下、右、上、左

假定傳入的店沒有走過且可以走通，將其值置為2，然后向下尋路，也就是將坐標(biāo) (i + 1, j) 傳入尋路方法中

進(jìn)行遞歸尋路，向下移動后，再次按照方向策略進(jìn)行尋路，即再向下尋路，直到遇到死路，即下右左均走不通（因為將走過的路置為2，故向上也走不通，即遇到死路時回頭不算通路），則將該點置為3，并返回false，回到上一個遞歸，找尋方向策略中剩下的方向，實現(xiàn)回溯

代碼實現(xiàn)：

public class Maze {
	public static void main(String[] args) {
		maze();
	}
	//迷宮回溯問題
	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)，則說明找到通路
	//0表示未走過，1表示墻，2表示可以走的通路，3表示已經(jīng)走過，但是走不通
	//確定方向策略：下 -> 右 -> 上 -> 左
	//若該點走不通，則回溯
	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)前點沒有走過
				map[i][j] = 2;    //假定該點可以走通
				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 {
					//該點走不通
					map[i][j] = 3;
					return false;
				}
			} else {
				//如果map[i][j] != 0
				//可能是1、2、3
				return false;
			}
		}
	}
}

輸出結(jié)果：

迷宮：
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

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之遞歸之迷宮回溯案例講解的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)之遞歸之迷宮回溯內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: