我正在嘗試使用 java 實現 4 路洪水填充問題。洪水填充算法維基百科問題：我有這個矩陣1 2 11 2 22 1 2現在我將選擇該矩陣的元素 (0,1) 并將洪水填充問題應用于此，以將滿足我的遞歸條件的所有 2 更改為 3。我的最終矩陣應該是：1 3 11 3 32 1 3我已經為此編寫了一個 java 代碼，但它給了我 StackOverflow 錯誤。誰能幫我弄清楚如何避免它。這是我的代碼：import java.util.*;public class abc {static void printarray(int a[][]){ for ( int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(a[i][j]+ " "); } System.out.println(); }}static void flood(int arr[][],int x,int y) { //base cases if (x < 0 || x >= 3 || y < 0 || y >= 3||arr[x][y] == 1) { return; } // i have made a dimension specific function but i can generalize it !. arr[x][y] = 3; flood(arr,x-1,y); flood(arr,x,y-1); flood(arr,x,y+1); flood(arr,x+1,y);}public static void main(String[] args) { int screen[][] = { {1, 2, 1}, {1, 2,2}, {2,1,2} }; flood(screen,0,1); printarray(screen);}錯誤：Exception in thread "main" java.lang.StackOverflowErrorat java.base/sun.nio.cs.UTF_8.updatePositions(UTF_8.java:79)at java.base/sun.nio.cs.UTF_8$Encoder.encodeArrayLoop(UTF_8.java:509)at java.base/sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:564)at java.base/java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:576)at java.base/sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:292)at java.base/sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:281)at java.base/sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)at java.base/java.io.OutputStreamWriter.write(OutputStreamWriter.java:211)at java.base/java.io.BufferedWriter.flushBuffer(BufferedWriter.java:120)at java.base/java.io.PrintStream.newLine(PrintStream.java:624)at java.base/java.io.PrintStream.println(PrintStream.java:772)at abc.flood(abc.java:19)at abc.flood(abc.java:30)at abc.flood(abc.java:30)at abc.flood(abc.java:33)at abc.flood(abc.java:30)at abc.flood(abc.java:33)
1 回答
呼喚遠方
TA貢獻1856條經驗 獲得超11個贊
您的問題出在這一行：
flood(arr,x-1,y);
flood(arr,x,y-1);
flood(arr,x,y+1);
flood(arr,x+1,y);
您在深度優先搜索中無條件地探索當前單元格的所有 4 個方向，當搜索在相同的兩個圖塊之間切換時，這會在某處創建無限遞歸循環。要解決這個問題，要么
跟蹤探索的單元格，不要重新訪問它們
進行廣度優先搜索而不是 DFS
進行迭代加深的深度優先搜索。
最簡單的方法是修改以下行
if (x < 0 || x >= 3 || y < 0 || y >= 3||arr[x][y] == 1) {
return;
}
改為返回 if arr[x][y] != 2，這有效地實現了選項 #1，通過阻止您探索已經轉換為 的單元格3，因為3 != 2它將導致它return。
if (x < 0 || x >= 3 || y < 0 || y >= 3||arr[x][y] != 2) {
return;
}
添加回答
舉報
0/150
提交
取消