Java數據結構 遞歸之迷宮回溯案例講解
更新時間：2021年08月03日 09:19:17 作者：去吧貓頭夜鷹
這篇文章主要介紹了Java數據結構遞歸之迷宮回溯案例講解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
問題介紹：
用二維數組表示一個迷宮，設置迷宮起點和終點，輸出迷宮中的一條通路
實現思路：
二維數組表示迷宮：
0表示路且未走過、1表示墻、2表示通路，3表示已經走過但走不通
設置尋路方法setWay，傳入地圖和坐標參數
默認方向策略：下、右、上、左
假定傳入的店沒有走過且可以走通，將其值置為2，然后向下尋路，也就是將坐標 (i + 1, j) 傳入尋路方法中
進行遞歸尋路，向下移動后，再次按照方向策略進行尋路，即再向下尋路，直到遇到死路，即下右左均走不通（因為將走過的路置為2，故向上也走不通，即遇到死路時回頭不算通路），則將該點置為3，并返回false，回到上一個遞歸，找尋方向策略中剩下的方向，實現回溯
代碼實現：
public class Maze {
public static void main(String[] args) {
maze();
}
//迷宮回溯問題
public static void maze() {
//創(chuàng)建二維數組模擬迷宮
//使用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("尋路結果：");
//開始尋路
setWay(map, 1, 1);
//輸出地圖
for (int[] row : map) {
for (int i : row) {
System.out.printf("%d\t", i);
}
System.out.println("");
}
}
//傳入地圖map
//傳入開始位置(i, j)
//如果能到達右下角(6, 5)，則說明找到通路
//0表示未走過，1表示墻，2表示可以走的通路，3表示已經走過，但是走不通
//確定方向策略：下 -> 右 -> 上 -> 左
//若該點走不通，則回溯
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {
//通路已經找到
return true;
} else {
if (map[i][j] == 0) {
//如果當前點沒有走過
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;
}
}
}
}
輸出結果：
迷宮： 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 尋路結果： 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
到此這篇關于Java數據結構之遞歸之迷宮回溯案例講解的文章就介紹到這了,更多相關Java數據結構之遞歸之迷宮回溯內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Spring MVC 是 Spring 提供的一個基于 MVC 設計模式的輕量級 Web 開發(fā)框架，本質上相當于 Servlet，Spring MVC 角色劃分清晰，分工明細。由于 Spring MVC 本身就是 Spring 框架的一部分，可以說和 Spring 框架是無縫集成2021-11-11
SSE簡單的來說就是服務器主動向前端推送數據的一種技術，它是單向的，也就是說前端是不能向服務器發(fā)送數據的。SSE適用于消息推送，監(jiān)控等只需要服務器推送數據的場景中，下面是使用Spring Boot來實現一個簡單的模擬向前端推動進度數據，前端頁面接受后展示進度條2022-11-11
springboot項目數據庫配置類DatabaseConfig示例詳解
這篇文章主要介紹了springboot項目數據庫配置類DatabaseConfig實現代碼,本文通過示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-08-08
springboot項目如何在linux服務器上啟動、停止腳本
這篇文章主要介紹了springboot項目如何在linux服務器上啟動、停止腳本問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
本文主要介紹了使用apache ant進行zip解壓縮操作的方法,可以解決中文編碼和首層父類無法創(chuàng)建問題,需要的朋友可以參考下2014-02-02
同步回調是一種在調用代碼中同步執(zhí)行回調函數的編程模式,在Java中,通過定義和實現接口來構建同步回調,本文就來介紹一下如何實現,具有一定的參考價值,感興趣的可以了解一下2024-09-09
這篇文章主要介紹了SpringBoot實現公共字段自動填充的方法步驟,文中通過代碼示例講解的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-11-11
使用jquery 的ajax 與 Java servlet的交互代碼實例
這篇文章主要介紹了使用jquery 的ajax 與 Java servlet的交互代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09
MyEclipse 2016 CI 4新增BootStrap模板
MyEclipse2016是一款全球使用最為廣泛的企業(yè)級開發(fā)環(huán)境程序,這篇文章主要介紹了MyEclipse 2016 CI 4新增BootStrap模板的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-06-06
Cookie?和?Session之間主要是通過?SessionId?關聯起來的,?SessionId是?Cookie?和?Session?之間的橋梁，這篇文章主要介紹了Java獲取Cookie和Session的方法,需要的朋友可以參考下2024-01-01