LeetCode 200. Number of Islands

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 200. Number of Islands 原题链接中等

作者：

wzc1995 , 2018-06-05 11:19:27 , 所有人可见 , 阅读 2806

14

3

题目描述

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

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

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

样例

算法

(深度优先遍历) $O(nm)$

从任意一个陆地点开始，即可通过四连通的方式，深度优先搜索遍历到所有与之相连的陆地，即遍历完整个岛屿。每次将遍历过的点清 0。
重复以上过程，可行起点的数量就是答案。

时间复杂度

由于每个点最多被遍历一次，故时间复杂度为 $O(mn)$。

空间复杂度

最坏情况下，需要额外 $O(mn)$ 的空间作为系统栈。

C++ 代码

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {-1, 0, 1, 0};

    void dfs(int x, int y, vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();

        grid[x][y] = '0';
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx >= m || ty < 0 || ty >= n)
                continue;

            if (grid[tx][ty] == '0')
                continue;

            dfs(tx, ty, grid);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if (m == 0)
            return 0;

        int n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(i, j, grid);
                }

        return ans;
    }
};

4 评论

stuq33 2022-06-19 14:11

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int res = 0;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (grid[i][j] == '1') {
                    q.push({i, j});
                    grid[i][j] = '0';
                    while (q.size()) {
                        int len = q.size();
                        for (int k = 0; k < len; k ++) {
                            auto t = q.front();
                            q.pop();
                            for (int u = 0; u < 4; u ++) {
                                int a = t.first + dx[u], b = t.second + dy[u];
                                if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == '1') {
                                    q.push({a, b});
                                    grid[a][b] = '0';
                                }

                            }
                        }
                    }
                    res ++;
                }     
            }
        }
        return res;
    }
};

有心人 2021-08-18 16:03

借楼贴一个BFS的解法hh，DFS 和 BFS 详解见详细题解：
- DFS：时间 O(mn), 空间 O(mn)
- BFS：时间 O(mn), 空间 O(min(m, n))

// bfs: 时间 O(mn), 空间 O(min(m, n))
class Solution {
public:
    vector<vector<char>> g;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 左-上-右-下

    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        int cnt = 0;
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[0].size(); j ++ )
                if (g[i][j] == '1') {
                    cnt ++ ;
                    bfs(i, j);
                }
        return cnt;
    }

    void bfs(int i, int j) {
        g[i][j] = '2';

        queue<pair<int, int>>q;
        q.push({i, j});

        while (!q.empty()) {
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;

            for (int k = 0; k < 4; k ++ ) {
                int a = x + dx[k], b = y + dy[k];
                if (a >= 0 && a < g.size() && b >= 0 && b <g[a].size() && g[a][b] == '1') {
                    q.push({a, b});
                    g[a][b] = '2'; // 这里是 '=', 一开始手残打成 "==", leetcode报超时
                }
            }
        }
    }
};