Mind palace

some thoughts

0%

1254. Number of Closed Islands

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

bfs O(mn) time O(min(m, n)) space
先顺四个边给open island灌水 然后遍历grid给每个closed island灌水并统计个数即可

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
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
                    bfs(grid, i, j);
                }
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 0) {
                    bfs(grid, i, j);
                    ++res;
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &grid, int r, int c) {
        queue<pair<int, int>> q;
        grid[r][c] = 1;
        q.emplace(r, c);
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || grid[rr][cc]) continue;
                grid[rr][cc] = 1;
                q.emplace(rr, cc);
            }
        }
    }

    int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
};
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
45
46
47
48
49
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                bfs(grid, i, 0);
            }
            if (grid[i][n - 1] == 0) {
                bfs(grid, i, n - 1);
            }
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 0) {
                bfs(grid, 0, j);
            }
            if (grid[m - 1][j] == 0) {
                bfs(grid, m - 1, j);
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 0) {
                    bfs(grid, i, j);
                    ++res;
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &grid, int r, int c) {
        queue<pair<int, int>> q;
        grid[r][c] = 1;
        q.emplace(r, c);
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || grid[rr][cc]) continue;
                grid[rr][cc] = 1;
                q.emplace(rr, cc);
            }
        }
    }

    int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
};