200.岛屿数量

题目:200.岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

• 示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

• 示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

• 提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

思路

1. 找到所有的’1’:

   • 遍历整个网格，找到所有的 '1'。
   • 对每个 '1'，调用 dfs 函数，将该岛屿淹没并计数。

2. 深度优先搜索 (DFS):

   • 将当前的 '1' 变为 '0'，表示已访问过。
   • 递归地检查相邻的四个方向（上、下、左、右）是否也是 '1'，并继续沉没它们。

• 时间复杂度:O(mn)
• 空间复杂度:O(mn)

代码

public int numIslands(char[][] grid) {
    int numIslands = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                // 岛屿数量加1
                numIslands++;
                // 使用DFS沉没这片岛屿
                dfs(grid, i, j);
            }
        }
    }
    return numIslands;
}

private void dfs(char[][] grid, int x, int y) {
    // 边界条件，判断当前坐标是否合法
    if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1 || grid[x][y] == '0') {
        return;
    }
    // 将当前陆地标记为水，表示已经访问过
    grid[x][y] = '0';
    // 递归检查相邻的四个方向
    dfs(grid, x - 1, y);
    dfs(grid, x + 1, y);
    dfs(grid, x, y - 1);
    dfs(grid, x, y + 1);
}