给定二维矩阵，找出矩阵中存在的连通 1 的岛数

Question

给定一个由 0 和 1 组成的矩阵。找出矩阵中存在的连通 1 的岛数。 注意：如果 1 周围有另一个 1（8 个方向中的任意一个），则称 1 是连通的。

我写了如下代码：

class Islands {

    // Function to find the number of island in the given list A
    // N, M: size of list row and column respectively
    static boolean isSafe(int i, int j, ArrayList<ArrayList<Boolean>> visited, int R, int C,ArrayList<ArrayList<Integer>> A){
        return ((i>=0 && i<R) && (j>=0 && j<C) && (A.get(i).get(j)==1) && (!visited.get(i).get(j)));
    }
    static void BFS(ArrayList<ArrayList<Integer>> A,ArrayList<ArrayList<Boolean>> visited,int x , int y){
        int[] x_pos = {-1,-1,-1,0,0,1,1,1};
        int[] y_pos = {-1,0,1,-1,1,-1,0,1};
        visited.get(x).add(y,true);
        for(int k=0;k<8;k++){
            if(isSafe(x+x_pos[k],y+y_pos[k],visited,A.size(),A.get(0).size(),A))
                BFS(A,visited,x+x_pos[k],y+y_pos[k]);
        }
    }
    
    static int findIslands(ArrayList<ArrayList<Integer>> A, int N, int M) {
        ArrayList<ArrayList<Boolean>> visited = new ArrayList<>();
        for(int i=0;i<N;i++) {
            visited.add(i,new ArrayList<Boolean>(M));
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                visited.get(i).add(j,false);
            }
        }
        int num = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if((A.get(i).get(j)==1) && (!visited.get(i).get(j))){
                    BFS(A, visited,i,j);
                    num++;
                }
            }
        }
        return num;
        
    }
}

对于测试用例

1 1 0

0 0 1

1 0 1

它返回 3 而不是 2。

调试的时候发现访问数组被修改成这样

真真假

假假真

false false true

真真假

假假真

真假假

真真假

假假真

真假真

我不明白的是我的代码的哪一部分将值 true 更改为 false（突出显示的部分）。 请提出建议。

Answer 1

Class ArrayList<E>

public void add(int index, E element)

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

See the documentation

发生的事情是，实际上你 push 最后的值，然后从

true true false

false false true

false false true

到

true true false

false false true

true false false true