LeetCode200、岛屿数量

题目描述

给你一个由 '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

题目解析

题目在说什么

想象你有一张地图，地图被分成了很多小格子。每个格子要么是“1”（代表陆地），要么是“0”（代表水）。 现在我们要数一数地图上有几块“岛屿”。 什么是岛屿呢？就是连在一起的陆地。注意，只有上下左右相邻的陆地才算连在一起，斜着的不算。 而且地图的四周都是水，所以不用担心岛屿会跑到地图外面去。

比如，地图上有一片陆地，它们上下左右连成一片，这就是一个岛屿。 如果另一片陆地跟这片隔了水，那就是另一个岛屿。

思路是怎么来的

我们可以这样想： 我站在地图上，从左上角开始，一个格子一个格子地看。 如果看到一个格子是“1”（陆地），而且我还没去过这个格子，那说明我找到了一座新岛屿的“起点”。 然后，我要把这座岛屿上所有的陆地都找出来，标记成“已去过”，这样下次再看到它们就不会重复计数了。

怎么找呢？就像玩“扫雷”游戏一样： 从起点开始，看看它上下左右四个方向有没有陆地。如果有，就继续看那个陆地的上下左右…… 这样一直找下去，直到把整座岛屿上所有的陆地都找遍。 这个过程就像“病毒传播”——从一个点开始，向四周扩散，直到没有新的陆地可去。

这就是“深度优先搜索”（DFS）或“广度优先搜索”（BFS）的思路。 DFS 就像走迷宫：一条路走到黑，走不通了再回头。 BFS 就像水波扩散：一圈一圈往外扩。

代码逐步拆解

我们以 DFS 的代码为例，一步一步看它在干什么。

1. 准备工具

private final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

这行代码定义了一个“方向数组”，表示上下左右四个方向。 为什么要这个？因为我们要知道从当前格子出发，往哪走才能到相邻格子。 比如 {0, 1} 表示行不变、列加1，也就是往右走。

2. 主函数 numIslands

int x = grid.length;    // 行数
int y = grid[0].length; // 列数
int ans = 0;            // 岛屿数量，初始为0
boolean[][] checkList = new boolean[x][y]; // 记录每个格子是否被访问过

这里我们创建了一个跟地图一样大的“打卡表” checkList。 每个格子一开始都是 false，表示还没去过。 ans 就是我们要找的答案——岛屿的数量。

3. 遍历每一个格子

for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        if (grid[i][j] == '1' && !checkList[i][j]) {
            DFS(grid, i, j, checkList);
            ans++;
        }
    }
}

我们从上到下、从左到右，一个一个格子检查。 如果这个格子是陆地（'1'）而且还没去过（!checkList[i][j]），那就说明我们发现了一座新岛屿。 于是我们调用 DFS 去把这座岛屿上所有的陆地都标记为“已去过”。 然后 ans++，岛屿数量加1。

4. DFS 函数：如何标记整座岛屿

private void DFS(char[][] grid, int i, int j, boolean[][] checkList) {
    checkList[i][j] = true;  // 先标记当前格子为已去过
    
    for (int[] dir : DIRECTIONS) {
        int next_i = i + dir[0];
        int next_j = j + dir[1];
        
        if (next_i >= 0 && next_i < grid.length && 
            next_j >= 0 && next_j < grid[0].length &&
            !checkList[next_i][next_j] && 
            grid[next_i][next_j] == '1') {
            DFS(grid, next_i, next_j, checkList);
        }
    }
}

这个函数做的事情很简单： 1. 把当前格子标记为“已去过”。 2. 看看上下左右四个方向有没有未去过、且是陆地的格子。