Java洪水问题堆栈溢出错误

Question

我正在尝试使用Java实现4条洪水问题。
洪水填充算法Wikipedia

问题：

我有这个矩阵

1 2 1
1 2 2
2 1 2

现在，我将选择此矩阵的元素（0,1），然后将洪水填充问题应用于此，以更改所有满足我的递归条件为3的2。

我的最后矩阵应该是：

1 3 1
1 3 3
2 1 3

我已经为此写了一个Java代码，但它给了我堆栈流的错误。任何人都可以帮助我弄清楚如何避免它。

这是我的代码：

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.StackOverflowError
at 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)

Answer 1

您的问题在此行：

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;
}

如果arr[x][y] != 2返回，则通过阻止您探索已经转换为3的单元格，这可以有效地实现选项＃1，因为3 != 2会导致其为return。

if (x < 0 || x >= 3 || y < 0 || y >= 3||arr[x][y] != 2) {
    return;
}