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

Question

“给出一个布尔2D矩阵，找到孤岛的数量。一组相连的1组成一个孤岛。”

在这个岛屿计数问题的变体中，我们要计算完全被水包围的岛屿的数目。也就是说，边缘不应该计算1，边缘也不应该计算孤岛。我们只希望1的所有边仅被0包围。

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

我还尝试过每次回溯时都减少计数，但这显然是徒劳的，因为最终计数小于零。最后，我尝试减少计数，同时将下限设置为0。这始终一直返回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。

最后一点-这些数组应在类级别（即静态）而不是在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 };