Java 2D数组包围

Question

我的任务是编写一个程序，如果在 2D 数组中 1-s 包围 0-s，则该程序返回 true。

我尝试过类似的方法，但找不到正确的解决方案。

    public boolean checkGameState(){
    for(int i=0;i<fields.length;i++){
        for(int j=0;j<fields.length;j++){
            if(fields[i][j]!=0){
                if(row(i,j){
                    return true;
                }
            }
        }
    }
    return false;

}

private boolean row(int a, int b){
    int checkI=a;
    int checkJ=b;
    while(fields[checkI][checkJ]==1){
        checkJ++;
    }
    while(fields[checkI][checkJ]==1){
        checkI++;
    }
    while(fields[checkI][checkJ]==1){
        checkJ--;
    }
    while(fields[checkI][checkJ]==1){
        checkI--;
    }
    return a==checkI && b==checkJ;
}

二维数组看起来像这样:

111100
100100
100101
111100
001100

对于该数组，该方法应返回 true。

Answer 1

最简单的方法可能是使用 flood fill算法消除所有没有被1包围的零，然后检查是否还有剩余。

首先，将二维数组“边缘”上的所有零直接放入队列中。然后，使用洪水填充算法将所有这些变成不同的数字(例如 2)，并将它们旁边的节点添加到边缘集(对角线或仅直接邻居)。重复此操作，直到边缘中不再有节点。最后，检查数组中是否还有零。如果是这样，那么它们与边缘区域没有连接，因此必须被“包围”。

// test data set up
int[][] data = {{1,1,1,1,0,0},
                {1,0,0,1,0,0},
                {1,0,0,1,0,1},
                {1,1,1,1,0,0},
                {0,0,1,1,0,0}};
int N = data.length, M = data[0].length;

// create queue of zeros on the "fringe"
Queue<int[]> fringe = new LinkedList<>();
for (int i = 0; i < N; i++) {
    if (data[i][0  ] == 0) fringe.add(new int[]{i,0  });
    if (data[i][M-1] == 0) fringe.add(new int[]{i,M-1});
}
for (int j = 0; j < M; j++) {
    if (data[0  ][j] == 0) fringe.add(new int[]{0  ,j});
    if (data[N-1][j] == 0) fringe.add(new int[]{N-1,j});
}   

// do flood fill until no more zeros reachable
while (! fringe.isEmpty()) {
    int[] next = fringe.poll();
    int i = next[0], j = next[1];
    data[i][j] = 2;
    for (int di = -1; di <= 1; di++) {
        for (int dj = -1; dj <= 1; dj++) {
            try {
                if (data[i+di][j+dj] == 0) fringe.add(new int[]{i+di, j+dj});
            } catch (ArrayIndexOutOfBoundsException e) {}
        }   
    }
}

// check for remaining zeros
boolean encircled = false;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        System.out.print(data[i][j]);
        encircled |= data[i][j] == 0;
    }   
    System.out.println();
}
System.out.println(encircled);   

示例输出:

111122
100122
100121
111122
221122
true

复杂度应该约为O(NxM)，因为每个NxM节点只能在队列中出现一次(加上一些开销构建队列并查找剩余的零)。