时间戳

首页 > 解决方案 > 计算具有变化的 2d 矩阵中的岛数

java - 计算具有变化的 2d 矩阵中的岛数

问题描述

“给定一个布尔二维矩阵，找出岛屿的数量。一组连接的 1 形成一个岛屿。”

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

我尝试使用流行的 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; 
    }

标签： javaalgorithmdepth-first-searchgaps-and-islands

解决方案

首先访问所有边缘单元格（顶部和底部行，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++;
        }
    }
}

请注意，您必须在此处而不是 in 中增加计数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 };

推荐阅读