VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 200. 岛屿数量

Posted on Edited on In , ,

摘要：
洪水灌溉算法经典题。

题目

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

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

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

输入：
{
{‘1’, ‘1’, ‘1’, ‘1’, ‘0’},
{‘1’, ‘1’, ‘0’, ‘1’, ‘0’},
{‘1’, ‘1’, ‘0’, ‘0’, ‘0’},
{‘0’, ‘0’, ‘0’, ‘0’, ‘0’}
}
输出： 1

示例2：

输入：
{
{‘1’, ‘1’, ‘0’, ‘0’, ‘0’},
{‘1’, ‘1’, ‘0’, ‘0’, ‘0’},
{‘0’, ‘0’, ‘1’, ‘0’, ‘0’},
{‘0’, ‘0’, ‘0’, ‘1’, ‘1’}
}
解释： 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

提示：

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

遍历整个网格，从每个’1’处开始向四个方向搜索，因为’0’不需要搜索，所以’0’既可以是题目中的海水也可以记录已遍历的岛屿，这样可以省去开一个新数组。
每一次搜索完毕，岛屿数量加一。因为岛屿和岛屿之间必然被水淹没，不可连通。
可以使用DFS和BFS两种写法。
这是一个经典的 Flood Fill 又称 洪水灌溉 算法，在图像处理领域有很大用途，扫雷游戏也使用了这个算法。

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
33
34
// 执行用时: 16 ms
// 内存消耗: 9.4 MB
class Solution {
public:
    vector<vector<char>> g;
    int m, n;
    int res = 0;
    const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++) {
                if (g[i][j] == '1') {
                    dfs(i, j);
                    res ++;
                }
            }
        }

        return res;
    }

    void dfs(int r, int c) {
        g[r][c] = '0';
        for (int i = 0; i < 4; i ++ ) {
            int ner = r + dr[i], nec = c + dc[i];
            if (ner >= 0 && ner < m && nec >= 0 && nec < n && g[ner][nec] == '1') {
                dfs(ner, nec);
            }
        }
    }
};
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
33
34
35
36
// 执行用时: 2 ms
// 内存消耗: 40.9 MB
class Solution {
    int[] dr, dc;
    char[][] g;
    int m, n;
    int res = 0;
    public int numIslands(char[][] grid) {
        g = grid;
        m = grid.length;
        n = grid[0].length;
        dr = new int[] {-1, 0, 1, 0};
        dc = new int[] {0, 1, 0, -1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '1') {
                    res ++;
                    dfs(i, j);
                }
            }
        }

        return res;
    }

    private void dfs(int r, int c) {
        g[r][c] = '0';
        for (int d = 0; d < 4; d++) {
            int ner = r + dr[d], nec = c + dc[d];
            if (ner >= 0 && ner < m && nec >= 0 && nec < n && g[ner][nec] == '1') {
                dfs(ner, nec);
            }
        }
    }
}

BFS

在Java语言中，可以使用当前行与列 i, j 和总列数 n 进行hash运算，将结果入队，以代替pair.
encode:
int hash = i * n + j;
decode:
int i = hash / n, j = hash % n;

另外，还有个值得注意的地方就是，每次根据当前岛屿计算出四个方向的下一个岛屿时，要预先将其设置成 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 执行用时: 16 ms
// 内存消耗: 10.2 MB
class Solution {
public:
    vector<vector<char>> g;
    int64_t m, n;
    const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
    int res = 0;
    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        m = g.size(), n = g[0].size();

        for (int i = 0; i < m; i++ ) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '1') {
                    res++;
                    bfs(i, j);
                }
            }
        }

        return res;
    }

    void bfs(int i, int j) {
        queue<pair<int, int>> q;
        q.push({i, j});
        g[i][j] = '0';
        
        for (; q.size();) {
            int r = q.front().first, c = q.front().second;
            q.pop();

            for (int d = 0; d < 4; d ++) {
                int ner = r + dr[d], nec = c + dc[d];
                if (ner >= 0 && ner < m && nec >= 0 && nec < n && g[ner][nec] == '1') {
                    q.push({ner, nec});
                    g[ner][nec] = '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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 执行用时: 3 ms
// 内存消耗: 40.9 MB
class Solution {
    int[] dr, dc;
    char[][] g;
    int m, n;
    int res = 0;
    public int numIslands(char[][] grid) {
        g = grid;
        dr = new int[] {-1, 0, 1, 0};
        dc = new int[] {0, 1, 0, -1};
        m = g.length;
        n = g[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '1') {
                    res++;
                    bfs(i, j);
                }
            }
        }

        return res;
    }

    private void bfs(int i, int j) {
        Queue<Integer> q = new LinkedList<>();
        q.add(i * n + j);
        g[i][j] = '0';

        for (; q.size() > 0;) {
            int hash = q.remove();
            int r = hash / n, c = hash % n;
            for (int d = 0; d < 4; d++) {
                int ner = r + dr[d], nec = c + dc[d];
                if (ner >= 0 && ner < m && nec >= 0 && nec < n && g[ner][nec] == '1') {
                    g[ner][nec] = '0';
                    q.add(ner * n + nec);
                }
            }
        }
    }
}

原题链接： LeetCode 200. 岛屿数量