岛屿数量

原题链接

使用的方法

深度优先搜索（DFS）

解题思路

• 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，我们需要计算岛屿的数量。岛屿被水包围，并且只能通过水平或垂直方向连接。
• 我们可以使用深度优先搜索（DFS）来解决这个问题。
• 首先，我们遍历整个网格，当我们遇到一个 '1' 时，说明我们找到了一个新的岛屿，我们将岛屿数量加一。然后，我们调用一个辅助函数 dfs 来将与当前岛屿相连的所有 '1' 都标记为 '0'，以避免重复计数。
• 在 dfs 函数中，我们首先检查当前坐标是否越界或者当前格子是否为 '0'，如果是，则返回。否则，我们将当前格子标记为 '0'，表示已经访问过了。然后，我们递归地调用 dfs 函数来访问当前格子上下左右的相邻格子。
• 通过这种方式，我们可以确保每个岛屿只被计数一次，并且我们最终返回岛屿的总数量。

代码实现

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int res = 0;

        for(int r=0;r< rows;r++){
            for(int c=0; c<cols;c++){
                if(grid[r][c] == '1'){
                    res++;
                    dfs(grid,r,c);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int r,int c){
        int rows = grid.length;
        int cols = grid[0].length;

        if(r < 0 || r >= rows || c<0 || c>=cols || grid[r][c] == '0')
            return;

        grid[r][c] = '0';
        dfs(grid,r-1,c);
        dfs(grid,r+1,c);
        dfs(grid,r,c-1);
        dfs(grid,r,c+1);
    }
}