Java中2d int数组优化的洪水填充

Question

我正在编写自己的 Flood Fill 实现。

我想出了这个代码：

  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.

它是维基伪代码的实现：

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要快得多，或者我的代码有问题。

问题是：它很慢。
我能对性能做些什么吗？我可以用内存换取性能，但原生递归让我得到了 stackoverflow。

Answer 1

好的，我们开始了:)。我用数组模拟了堆栈，我希望它会快得多。我没有完全遵循伪代码，但它有效，我认为它应该很快。

public static void main(String[] args) {
    int testArray[][] = new int[10][10];
    for (int i = 0; i < 10; i++) {
        testArray[i][i] = 1;
        testArray[9-i][i] = 1;
    }
    testArray[4][7] = 1;

    System.out.println("Array before");

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            System.out.print(testArray[j][i] + " ");
        }
        System.out.println("");
    }

    fillArea(6,8,0,7,testArray);

    System.out.println("Array after");
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            System.out.print(testArray[j][i] + " ");
        }
        System.out.println("");
    }
}

 public static void fillArea(int x, int y, int original, int fill, int[][] arr) {
     int maxX = arr.length - 1;
     int maxY = arr[0].length - 1;
     int[][] stack = new int[(maxX+1)*(maxY+1)][2];
     int index = 0;         

     stack[0][0] = x;
     stack[0][1] = y;
     arr[x][y] = fill;

     while (index >= 0){
         x = stack[index][0];
         y = stack[index][1];
         index--;            

         if ((x > 0) && (arr[x-1][y] == original)){
             arr[x-1][y] = fill;
             index++;
             stack[index][0] = x-1;
             stack[index][1] = y;
         }

         if ((x < maxX) && (arr[x+1][y] == original)){
             arr[x+1][y] = fill;
             index++;
             stack[index][0] = x+1;
             stack[index][1] = y;
         }

         if ((y > 0) && (arr[x][y-1] == original)){
             arr[x][y-1] = fill;
             index++;
             stack[index][0] = x;
             stack[index][1] = y-1;
         }                

         if ((y < maxY) && (arr[x][y+1] == original)){
             arr[x][y+1] = fill;
             index++;
             stack[index][0] = x;
             stack[index][1] = y+1;
         }                          
     }
 }

此代码具有此输出：

Array before
1 0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 1 0 1 0 0 1 0 0 
0 1 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 0 1 
Array after
1 0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 1 7 7 1 0 0 0 
0 0 1 7 1 7 7 1 0 0 
0 1 7 7 7 7 7 7 1 0 
1 7 7 7 7 7 7 7 7 1