岛屿数量

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

https://leetcode.cn/problems/number-of-islands/description/

DFS加递归

碰到一块陆地，顺着上下左右一路 “淹掉” 所有连在一起的陆地，每启动一次淹水，就代表找到了一座新岛屿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int numIslands(char[][] grid) {
    int count = 0;
    int m = grid.length;
    if (m == 0) return 0;
    int n = grid[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 找到一块未访问陆地，岛屿+1，开始洪水填充
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j, m, n);
            }
        }
    }
    return count;
}

// DFS：淹没(i,j)连通的全部陆地
void dfs(char[][] grid, int i, int j, int m, int n) {
    // 递归出口：越界 OR 不是陆地
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    // 标记已访问
    grid[i][j] = '0';
    // 四个方向深度搜索
    dfs(grid, i - 1, j, m, n);
    dfs(grid, i + 1, j, m, n);
    dfs(grid, i, j - 1, m, n);
    dfs(grid, i, j + 1, m, n);
}