简单的洪水填充方法导致 StackOverFlow 错误

Question

我的洪水填充方法：

public void fillNeighbours(int x, int y) {
    for(int i = -1; i < 2; i++) {
        for(int j = -1; j < 2; j++) {
            try {
                visible[x+i][y+j] = true;

                if(num[x+i][y+j] == 0) {
                    fillNeighbours(x+i, y+j);
                }
            } catch (ArrayIndexOutOfBoundsException ignored) {}
        }
    }
}

catch (ArrayIndexOutOfBoundsException ignored) {} 是为了避免 x and/or y 位置超出数组范围。数组大小为 30 x 30。我正在制作扫雷游戏。所以你可能知道我为什么需要这个方法以及它应该如何工作。如果你不知道扫雷是什么，那么这里有关于该游戏的快速视频：Introduction to minesweeper

Answer 1

您似乎在递归调用 fillNeighbours 而没有任何 break out 子句（基本情况），因此调用填满了堆栈。

来自 Wikistack

递归的树定律是

递归算法必须有一个基本情况。
一种递归算法必须改变其状态并向基本情况移动。
一个递归算法必须递归地调用自身。

Answer 2

一旦 fillNeighbours 找到一个单元格并调用自己，下一个循环将始终在 i 和 j 等于 0 时调用另一个单元格。所以它永远不会退出，一旦堆栈已满就会崩溃。

除此之外，它会生成一棵非常深的树，因为它不会跟踪哪些单元格已被递归，并且会多次调用同一单元格上的 fillNeighbours。

Answer 3

代码重新访问已设置为可见的字段。

试试

if(!visible[x+i][y+j]){
  visible[x+i][y+j] = true;
  if(num[x+i][y+j] == 0) {
    fillNeighbours(x+i, y+j);
  }
}

简单的洪水填充方法导致 StackOverFlow 错误

Simple flood fill method causes StackOverFlow error

java

arrays

stack-overflow

flood-fill

minesweeper