计算机科学基础leetcode刷题图
Source
Edit
History

1020. 飞地的数量

Problem: 1020. 飞地的数量

Reference

代码随想录 (programmercarl.com)

思路

本题仍然采用深度优先搜索算法。

由于心情急躁不安，这两处错误,将范围写反了，一直没有看出来，遍历列应该用列数量，遍历行应该用行数量。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < rowNum; i++) {//此处错误
    if (grid[0][i] == 1)
        dfs(grid, 0, i);
    if (grid[rowNum - 1][i] == 1)
        dfs(grid, rowNum - 1, i);
}
for (int i = 0; i < column; i++) {//此处错误
    if (grid[i][0] == 1)
        dfs(grid, i, 0);
    if (grid[i][columnNum - 1] == 1)
        dfs(grid, i, columnNum - 1);
}

最后重置计数，再遍历飞地的地块数量。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
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
class Solution {
public:
    int rowNum;
    int columnNum;
    int cnt;
    void dfs(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = 0;
        cnt++;
        pair<int, int> neigbors[4]{
            pair<int, int>(x, y + 1), pair<int, int>(x + 1, y),
            pair<int, int>(x, y - 1), pair<int, int>(x - 1, y)};
        for (auto item : neigbors) {
            if (item.first < 0 || item.first >= rowNum || item.second < 0 ||
                item.second >= columnNum)
                continue;
            if (grid[item.first][item.second] == 0)
                continue;
            dfs(grid, item.first, item.second);
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
        rowNum = grid.size();
        columnNum = grid[0].size();
        for (int i = 0; i < columnNum; i++) {
            if (grid[0][i] == 1)
                dfs(grid, 0, i);
            if (grid[rowNum - 1][i] == 1)
                dfs(grid, rowNum - 1, i);
        }
        for (int i = 0; i < rowNum; i++) {
            if (grid[i][0] == 1)
                dfs(grid, i, 0);
            if (grid[i][columnNum - 1] == 1)
                dfs(grid, i, columnNum - 1);
        }
        cnt = 0;
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < columnNum; j++) {
                if (grid[i][j] == 1)
                    dfs(grid,i,j);
            }
        }
        return cnt;
    }
};