数组索引超出边界异常 floodfill java

Question

我正在尝试使用 floodfill 计算二维数组中零的个数，但我得到的是 ArrayIndexOutOfBoundsException。这是我到目前为止所做的。我评论了错误所在。

public class floodfill {

    public static int[][] input = new int[][]{
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    public static int count = 0;

    public static void main(String[] args) {
        int row = input.length;
        int col = input[0].length;
        System.out.println("" + row);
        System.out.println("" + col);

        apply(row, col);

    }

    private static void apply(int x, int y) {
        int currentColor = getValueAt(x, y);
        if (currentColor == 0) {
            count++;
            apply(x + 1, y);
            apply(x - 1, y);
            apply(x, y + 1);
            apply(x, y - 1);
        }
    }

    private static int getValueAt(int x, int y) {
        if (x < 0 || y < 0 || x > input.length || y > input[x].length) {
            return -1;
        } else {
            return input[x][y];
        }
    }

}

Answer 1

这里的问题是，当转到 getValueAt 时，您传递的是数组长度，并且数组索引在 .length - 1 处停止。参数 1 太多了……如果你的 'if' 语句是正确的，它就不会抛出错误：

// Add equal sign to last 2 conditions
if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
    return -1;
}

其他小东西：

始终将您的 class 姓名大写，即 Floodfill 或 FloodFill；
在 'if' 语句 returns.

Answer 2

我正在查看您的 getValueAt 函数，发现边界条件不准确。数组元素的索引从 0 到数组长度减 1，如果您尝试访问这些限制之外的元素，您将得到一个异常。尝试在您的 getValueAt 函数中使用以下代码：

private static int getValueAt(int x, int y) {
    if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
        return -1;
    } else {
        return input[x][y];
    }
}

此外，我建议将您的初始申请更改为在范围内，因为 array.length 或 array[x].length 不在范围内。

Answer 3

除了数组索引检查中指出的错误（在 >= 数组长度时终止，而不是在大于长度时终止），您的递归将永远不会终止，您将要体验一些非常有趣的堆栈溢出错误。

进入单元格后，您需要将值从 0 更改为其他值（例如 1）。我建议添加一个 visit 方法来处理这个问题：

private static void visit(int x, int y) {
    input[x][y] = 1;
}

您可以在 apply 内调用它，在您的 if 块内。最后，您可能应该从第一个节点 apply(0, 0) 开始，然后向外工作 (x+1, y+1), (x, y+1), (x+1, y)；没有理由从当前索引中减去，因为之前的单元格已经被访问过。

private static void apply(int x, int y) {
    int currentColor = getValueAt(x, y);
    if (currentColor == 0) {
        visit(x, y);
        count++;
        apply(x + 1, y + 1);
        apply(x + 1, y);
        apply(x, y + 1);
    }
}

演示

下面是这个更新算法运行ning 的简单可视化（在浏览器中移植到 JS 到运行，但语法非常相似，你会理解它——你可以忽略特定于可视化的代码）。

$(function() {
    var input = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ];

    var count = 0;

    function main() {
        var row = 0, col = 0;
        apply(row, col);
        console.log(count);
    };

    function apply(x, y) {
        var currentColor = getValueAt(x, y);
        if (currentColor == 0) {
            visit(x, y);
            count++;
            apply(x + 1, y + 1);
            apply(x + 1, y);
            apply(x, y + 1);
        }
    }

    function getValueAt(x, y) {
        if (x < 0 || y < 0 || x >= input.length || y >= input[x].length) {
            return -1;
        } else {
            return input[x][y];
        }
    }

    function visit(x, y) {
        setTimeout(function() {
           $(("#child" + x) + y).css("background-color", "pink");
        }, 170 * x + 170 * y);
        input[x][y] = 1;
    }

    function visualize() {
        for (var i = 0; i < input.length; i++) {
            $("<div />", {
                "id" : "row" + i
            }).appendTo("#parent");

            for (var j = 0; j < input[i].length; j++) {

                $("<div />", {
                    "class" : "child",
                    "id" : ("child" + i) + j
                }).appendTo("#row" + i);
            }
        }
    }

    visualize();
    main();
});

.child {
 width: 25px;
 height: 25px;
 background-color: yellow;
 border: 1px solid black;
 margin: 1px;
 display: inline-block;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<div id="parent"></div>

数组索引超出边界异常 floodfill java

array index out of boundary exception floodfill java

java

arrays

flood-fill

indexoutofboundsexception

演示