LeetCode200-岛屿的个数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/number-of-islands/

中文链接：https://leetcode-cn.com/problems/number-of-islands/

题目详述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 3

题目详解

DFS。

  • 找到 grid[i][j] == '1' 的地方，则找到一个连通块。
  • 从这个位置尝试往上下左右四个方向搜索，遍历整个连通块，令 grid[i][j] = '0' 。
  • 用一个变量来记录连通块的个数。
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
public class LeetCode_00200 {

    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';
        if (i - 1 >= 0 && grid[i - 1][j] == '1')
            dfs(grid, i - 1, j);
        if (i + 1 <grid.length && grid[i + 1][j] == '1')
            dfs(grid, i + 1, j);
        if (j - 1 >= 0 && grid[i][j - 1] == '1')
            dfs(grid, i, j - 1);
        if (j + 1 < grid[0].length && grid[i][j + 1] == '1')
            dfs(grid, i, j + 1);
    }
}