计算具有变化的二维矩阵中的岛屿数

Question

"Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island."

在这个计算岛屿数量问题的变体中，我们要计算完全被水包围的岛屿数量。即边缘的1不计入，边缘的孤岛也不计入。我们只希望 1 四周只被 0 包围。

我尝试使用流行的 dfs 技术并进行一些修改。我不遍历矩阵的所有边缘。这显然只能满足少数情况。以下示例失败，因为它 returns 2 而不是 1:

我也试过每次回溯时减少计数，但这显然是徒劳的，因为计数最终小于零。最后，我尝试减少计数，同时将下限设置为 0。这一直都是 returns 0。我肯定错过了什么。有帮助吗？

下面是代码：

class Islands { 
    // No of rows and columns 
    static final int ROW = 5, COL = 5; 
    int gcount;

    // A function to check if a given cell (row, col) can 
    // be included in DFS 
    boolean isSafe(int M[][], int row, int col, 
                   boolean visited[][]) 
    { 
        // row number is in range, column number is in range 
        // and value is 1 and not yet visited 
        return (row >= 1) && (row < ROW-1) && (col >= 1) && // used to be row >= 0 && row < ROW && col >=0
                (col < COL-1) && (M[row][col] == 1 && !visited[row][col]); //col < COL
    } 

    // A utility function to do DFS for a 2D boolean matrix. 
    // It only considers the 8 neighbors as adjacent vertices 
    void DFS(int M[][], int row, int col, boolean visited[][]) 
    { 
        // These arrays are used to get row and column numbers 
        // of 8 neighbors of a given cell 
        int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 }; 
        int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 }; 

        // Mark this cell as visited 
        visited[row][col] = true; 

        // Recur for all connected neighbors 
        for (int k = 0; k < 8; ++k) 
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) {
                System.out.println("here");
                ++gcount;
                DFS(M, row + rowNbr[k], col + colNbr[k], visited);
            }
            /*else {
                gcount--;
                if(gcount < 1) {
                    gcount = 0;
                }
            }*/
    } 

    // The main function that returns count of islands in a given 
    // boolean 2D matrix 
    int countIslands(int M[][]) 
    { 
        // Make a bool array to mark visited cells. 
        // Initially all cells are unvisited 
        boolean visited[][] = new boolean[ROW][COL]; 

        // Initialize count as 0 and traverse through the all cells 
        // of given matrix 
        int count = 0; 
        for (int i = 1; i < ROW-1; ++i) //I changed this from ROW
            for (int j = 1; j < COL-1; ++j) //I changed this from COL
                if (M[i][j] == 1 && !visited[i][j]) // If a cell with 
                { // value 1 is not 
                    // visited yet, then new island found, Visit all 
                    // cells in this island and increment island count 
                    DFS(M, i, j, visited); 
                    //++gcount; 
                } 

        return gcount; 
    }

Answer 1

在countIslands中首先访问所有边缘单元格（顶行和底行，左列和右列）。这会将所有可从边缘单元到达的岛屿标记为已访问。

for (int j = 0; j < COL; ++j)
{
    if (M[0][j] == 1 && !visited[0][j])
        DFS(M, 0, j, visited);
    if (M[ROW - 1][j] == 1 && !visited[ROW - 1][j])
        DFS(M, ROW - 1, j, visited);
}

for (int i = 1; i < ROW - 1; ++i) // I changed this from ROW
{
    if (M[i][0] == 1 && !visited[i][0])
        DFS(M, i, 0, visited);
    if (M[i][COL - 1] == 1 && !visited[i][COL - 1])
        DFS(M, i, COL - 1, visited);
}

然后像现在一样访问内部单元格。

int count = 0;
for (int i = 1; i < ROW - 1; ++i)
{
    for (int j = 1; j < COL - 1; ++j)
    {
        if (M[i][j] == 1 && !visited[i][j])
        {
            DFS(M, i, j, visited);
            count++;
        }
    }
}

请注意，您必须在此处增加计数，而不是在 DFS 中，因为 DFS 也被称为边缘岛。

最后一点 - 这些数组应该在 class 级别声明，即静态，而不是在 DFS 方法中。没有必要在每次递归调用时都创建它们。

    int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 }; 
    int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };

计算具有变化的二维矩阵中的岛屿数

Count number of islands in a 2d matrix with variation

java

algorithm

depth-first-search

gaps-and-islands