啊哈算法之解救小哈 -开发者知识库
簡述
本算法摘選自啊哈磊所著的《啊哈！算法》第四章第二節的題目——DFS算法解救小哈。文中代碼使用C語言編寫，博主通過閱讀和理解，重新由Java代碼實現了一遍，以此來加深對DFS算法的印象。
游戲設置
迷宮由n行m列的單元格組成（n和m小於等於50），每個單元格要么是空地要么是障礙物，障礙物是不能通行的，要求從迷宮起點開始找到一條通往迷宮中某個點的最短路徑。
解法思路
首先用一個二維數組來存儲迷宮，剛開始假設從迷宮入口（0, 0）開始，目標位置在（q, p），此行目的就是找到從（0, 0）到（q, p）的最短路徑。如果從入口的點，那么下一步只能是往右或者往下走，如果是到了迷宮中間的某個點，那么可能是往上下左右四個方向走，只能一個個去嘗試，索性我們這里就定義個順序，按照順時針（即右、下、左、上）的方向逐個嘗試。
還有一個問題值得注意，就是已經路過的點，肯定是不需要計算在接下來嘗試的點上了，這里為了方便判斷，可以利用熟悉的桶來標記，已經經過的點都標記在桶里，使用完之后回來再清理桶標記位就行了。對於障礙物，遇到障礙物就換個方向重新開始，這里就是重新返回到下一次遞歸循環就行了。
注意，當我們遍歷之后找到了目標點位，但可能不是到達所使用的最短路徑，所以在找到目標點位之后，需要返回重新嘗試從其他的方向尋找，直到把所有的可能性都嘗試完了，最后才把最短的那條路徑輸出來。
現在我們使用深度優先搜索算法DFS來嘗試實現這個算法。先從dfs函數開始，思考當前步驟是什么樣的，下一步和當前步驟是一樣的，邊界條件是什么樣的。
我們給dfs函數定義三個參數x、y和step，分別表示下一步達到的坐標以及當前步數，如果判斷已經找到目標位置，即判斷(x, y)是否與目標位置相等即可，同時用當前所走的step數去判斷是否是最小步數，是則更新記錄到最小步數值。
在具體的代碼實現中，我們還應該關注到如何從順時針的四個方向上開始搜索目標，如何定位到下一個點位，同時判斷是否越界，或者是否是障礙物、或者該點位之前已經路過等等之類的問題。
代碼實現
1 public class MazeDfs { 2 3 /** 迷宮矩陣的大小：n行 m列 */ 4 private static final Integer n = 10, m = 10; 5 /** 迷宮中的目標位置 */ 6 private static final Integer q = 6, p = 6; 7 /** 從起點到目標位置所行的最小步數 */ 8 private static Integer minStep = 999; 9 /** 迷宮地圖 */ 10 private static int[][] maze = new int[50][50]; 11 /** 桶，記錄步行經過的路徑位置 */ 12 private static int[][] book = new int[50][50]; 13 14 /** 15 * 遞歸函數 16 * 往前走一步，查看當前位置是否目標位置，否則繼續往下一個方向前進 17 * @param x 18 * @param y 19 * @param step 20 */ 21 public void dfs(int x, int y, int step) { 22 // 定義四個方向，依照順時針方向，依次向右、向下、向左、向上 23 int[][] next = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 24 25 System.out.println("當前坐標點：" x " " y); 26 27 // 判斷是否到達目標位置 28 if(x == q && y == p) { 29 // 更新最小步數值 30 if(step < minStep) { 31 minStep = step; 32 } 33 // 按照當前方式找到，則返回，換其他方式繼續找 34 return; 35 } 36 37 // 枚舉四個方向的找法 38 int tx, ty, k; 39 for(k = 0; k < 4; k ) { 40 // 計算出下一個步入的點的位置 41 tx = x next[k][0]; 42 ty = y next[k][1]; 43 44 // 判斷這個方向的下一步是否越界 45 if(tx < 0 || tx >= n || ty < 0 || ty >= m) { 46 continue; 47 } 48 49 // 判斷該點是否為障礙物或者剛才已經路過 50 if(maze[tx][ty] == 0 && book[tx][ty] == 0) { 51 // 標記這個點已經路過 52 book[tx][ty] = 1; 53 // 接着嘗試下一個點 54 dfs(tx, ty, step 1); 55 // 嘗試結束，取消這個點的標記 56 book[tx][ty] = 0; 57 } 58 } 59 return; 60 } 61 62 public static void main(String[] args) { 63 MazeDfs mazeDfs = new MazeDfs(); 64 // 初始化，把迷宮矩陣用二維數組表示出來，空地用“0”表示，障礙物用“1”表示 65 // TODO 66 67 // 從起點開始搜索，這里假設起點位置[0, 0]，開始時步數為0 68 int startx = 0, starty = 0, step = 0; 69 // 在桶中標記起點已經歷 70 book[startx][starty] = 1; 71 // 從第一個位置開始 72 mazeDfs.dfs(startx, starty, step); 73 74 // 輸出最少步數 75 System.out.println(String.format("從起點開始最少經過%d步可以到達目標位置。", minStep)); 76 } 77 78 }
最佳答案：
作者信息
