迷宮

題目要求

P1605題目鏈接

分析

我的思路還比較容易理解，但確實開的數組太多了（最終代碼）。
我想開一個遞歸的DFS搜索，對越界情況進行淘汰 （話說這能算剪枝嗎） ，再就是只允許在沒被標記為已遍歷的地方行進。
DFS用好了確實能搜出結果，但過程中遇到過一個大問題，下面就對此說明。

原先的代碼是這樣的：

import java.util.Scanner;public class Main {private static int x1, y1, x2, y2;private static int dfs(int x, int y, boolean[][] graph) {if (x < x1 || x > x2 || y < y1 || y > y2 || graph[x][y]) {return 0;} else if (x == x2 && y == y2) {return 1;}graph[x][y] = true;return dfs(x-1, y, graph) + dfs(x+1, y, graph) + dfs(x, y-1, graph) + dfs(x, y+1, graph);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt(), n = scanner.nextInt(), num = scanner.nextInt();x1 = scanner.nextInt();y1 = scanner.nextInt();x2 = scanner.nextInt();y2 = scanner.nextInt();boolean[][] graph = new boolean[m+1][n+1];for (int i = 0; i < num; i++) {graph[scanner.nextInt()][scanner.nextInt()] = true;}scanner.close();System.out.println(dfs(x1, y1, graph));}}

獲取了測試數據2：
in

5 5 5 1 2 5 5 2 1 2 2 2 3 2 4 3 4

out

10

自己在紙上推演了一段時間，發現是由于這個數據挺刁鉆（其實不過分啊），卡住了一個口子，所以我的程序就走不進去了。本質上的錯誤是：忽略了Java數組傳引用這個事情。
之前，我寫過一篇博客：《探究Java方法的參數傳遞是值傳遞還是引用傳遞》。我承認，里面有的結論我也不是100%確定，但確實也是被這個題逼得沒辦法。

正因為傳的是引用，至少也說明可以改引用，所以我們就很難處理了：一次的遍歷就可能“堵上道路”，讓其他的遞歸情況沒法進行。
事實上，我們要想遞歸的同時還開深拷貝的專屬標記數組，成本是很高的。

但我也沒別打法子，看了看測試范圍，很小，那就咬咬牙開數組copy吧（當時對數組拷貝的策略領會的不是很好，可以看這篇文章——《總結Java數組的拷貝和輸出》）。

當然了，其實在這種小數組范圍內，直接復制很簡單也很方便。

AC代碼（Java語言描述）

import java.util.Scanner;public class Main {private static int x2, y2, m, n;private static int dfs(int x, int y, boolean[][] graph) {if (x < 1 || x > m || y < 1 || y > n || graph[x][y]) {return 0;} else if (x == x2 && y == y2) {return 1;}graph[x][y] = true;boolean[][] array1 = new boolean[m+1][n+1];boolean[][] array2 = new boolean[m+1][n+1];boolean[][] array3 = new boolean[m+1][n+1];boolean[][] array4 = new boolean[m+1][n+1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {array1[i][j] = graph[i][j];array2[i][j] = graph[i][j];array3[i][j] = graph[i][j];array4[i][j] = graph[i][j];}}return dfs(x-1, y, array1) + dfs(x+1, y, array2) + dfs(x, y-1, array3) + dfs(x, y+1, array4);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);m = scanner.nextInt();n = scanner.nextInt();int num = scanner.nextInt();int x1 = scanner.nextInt();int y1 = scanner.nextInt();x2 = scanner.nextInt();y2 = scanner.nextInt();boolean[][] graph = new boolean[m+1][n+1];for (int i = 0; i < num; i++) {graph[scanner.nextInt()][scanner.nextInt()] = true;}scanner.close();System.out.println(dfs(x1, y1, graph));}}

總結

以上是生活随笔為你收集整理的DFS破解“迷宫问题”（洛谷P1605题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。