Java中二维int阵列优化的洪水填充

Question

我正在写我自己的“洪水填充”的实现。

我想出了一个密码：

  public static void fillArea(int x, int y, int original, int fill, int[][] arr) {
        Stack<int[]> q = new Stack<int[]>();
        int[] w = new int[2]; //to the west
        int[] e = new int[2]; //to the east

        if (arr[x][y] != original) {
            return;
        }

        q.push(new int[]{x, y});

        while (!q.isEmpty()) {
            int[] pos = (int[]) q.pop();
            int i = pos[0];
            int j = pos[1];
            if (arr[i][j] == original) {
                e[0] = i;
                e[1] = j;
                w[0] = i;
                w[1] = j;
            }


            while (w[1] > 0 && arr[w[0]][w[1] - 1] == original) { // to the west
                w[1] -= 1;
            }

            while (e[1] < arr[0].length - 1 && arr[e[0]][e[1] + 1] == original) { // to the east
                e[1] += 1;
            }

            for (int a = w[1]; a <= e[1]; a++) { // for every point between west and east
                arr[w[0]][a] = fill;


                if (w[0] > 0 && arr[w[0] - 1][a] == original) { //check if we can go north
                    q.push(new int[]{(w[0] - 1), a});
                }

                if (w[0] < arr.length - 1 && arr[w[0] + 1][a] == original) {//check if we can go south 
                    q.push(new int[]{(w[0] + 1), a});
                }

            }


        }
        return;
    }

伙伴关系是：

start point coords, value we want to change, new value we want to see as a result of filling, original array.

它是Wiki伪码的实现

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to Q.
 4. For each element N of Q:
 5.     If the color of N is equal to target-color:
 6.         Set w and e equal to N.
 7.         Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.         Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.         For each node n between w and e:
10.             Set the color of n to replacement-color.
11.             If the color of the node to the north of n is target-color, add that node to Q.
12.             If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.

我使用的是Stack而不是Queue，因为Stack看起来要快得多，或者我的代码有问题。

问题是:这是非常慢。

我能为表演做些什么吗？我可以用内存来交换性能，但是本机递归会导致堆栈溢出。

Answer 1

这个版本更快

public static void floodFill(int y, int x, byte originalvalue, byte newvalue, byte[][] arr) {
    Deque queue = new ArrayDeque();
    queue.add(new int[]{y, x});
    while (!queue.isEmpty()) {
        int[] t = (int[]) queue.poll();
        y = t[0];
        x = t[1];
        if (arr[y][x] == originalvalue) {
            arr[y][x] = newvalue;
            for (int i = 0; i
                    < 8; i++) {
                if (x + dx[i] < arr[0].length && y + dy[i] < arr.length && x + dx[i] > -1 && y + dy[i] > -1 && arr[y + dy[i]][x + dx[i]] == originalvalue) {
                    queue.add(new int[]{y + dy[i], x + dx[i]});
                }
            }
        }
    }
}