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

200. 岛屿数量

Problem: 200. 岛屿数量

警告

1
2
void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x, int y)
														↑←就是这个&搞了我将近半个小时,妈的傻逼
1
2
3
4
5
6
↓←这里不要用& 除非像下面这么写 这个pop要在取得x y之后
        auto item = queue.front();queue.pop();
        int x = item.first,y = item.second;
        
        auto item = queue.front();
        int x = item.first,y = item.second;queue.pop();

Reference

https://www.programmercarl.com/0200.%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F.%E5%B9%BF%E6%90%9C%E7%89%88.html#%E6%80%9D%E8%B7%AF

思路

注意本题中有大量打印信息，用来辅助理解，必要请删除

  1. 方法一bfs

本题使用广度优先搜索算法，使用队列来实现，不了解bfs请观看上面链接。

要注意的点是剔除条件，比如边界条件>= 列数，>= 行数，< 0，比如陆地条件grid[x][y] != '1'比如已经添加进入队列visited[x][y]，其实这里的visited更像是记录有没有加入队列，而不是有没有访问。

因为用其他数据结构而不是queue的话可以用find来查询。

  1. 方法二

也可以使用深度优先，本质上都是标记visited，过的地块。

写起来比bfs还要简洁一些。

复杂度

时间复杂度:

添加时间复杂度, 示例： $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
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x, int y) {
        //访问过了 return
        if (visited[x][y]) return;
        //设为访问过了
        visited[x][y] = true;
        //找到相邻节点
        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 (pair<int, int>& item : neigbors) {
            //越界
            if (item.first < 0 || item.first >= grid.size() || item.second < 0 || item.second >= grid[0].size()) continue;
            //陆地
            if (grid[item.first][item.second] == '0') continue;
            //访问
            if (visited[item.first][item.second]) continue;
            dfs(grid, visited,item.first, item.second);
        }
    }
    void bfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x, int y) {
        queue<pair<int, int>> queue;
        queue.push(pair<int, int>(x,y));
        while(!queue.empty()) {
            auto item = queue.front();queue.pop();
            int x = item.first,y = item.second;
            //访问过了 continue
            if(visited[x][y]) continue;
            //设为访问过了
            visited[x][y] = true;
            //找到相邻节点
            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 (pair<int, int>& item : neigbors) {
                //越界
                if (item.first < 0 || item.first >= grid.size() || item.second < 0 || item.second >= grid[0].size()) continue;
                //陆地
                if (visited[item.first][item.second]) continue;
                //访问
                if (grid[item.first][item.second] == '0') continue;
                queue.push(item);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),false));
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if(!visited[i][j] && grid[i][j] == '1') { 
                    bfs(grid,visited,i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

BFS

[]
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    vector<vector<bool>> visted;
    int ROWCNT;   // 行数
    int CLOWNCNT; // 列数
    void bfs(int x, int y, vector<vector<char>>& grid) {
        queue<pair<int, int>> queue;
        queue.push(pair<int, int>(x, y));
        visted[x][y] = true;
        cout << x;
        cout << "--";
        cout << y;
        cout << endl;
        while (!queue.empty()) {
            pair<int, int> cur = queue.front();
            queue.pop();
            // 得到临近节点
            pair<int, int> neigbors[4]{
                pair<int, int>(cur.first, cur.second + 1), // neigbor_up
                pair<int, int>(cur.first, cur.second - 1), // neigbor_down
                pair<int, int>(cur.first - 1, cur.second), // neigbor_left
                pair<int, int>(cur.first + 1, cur.second)  // neigbor_right
            };
            // 遍历临近节点
            for (pair<int, int> neigbor : neigbors) {
                // 剔除边界
                if (neigbor.first >= ROWCNT || neigbor.second >= CLOWNCNT ||
                    neigbor.first < 0 || neigbor.second < 0)
                    continue;
                // 剔除海洋
                if (grid[neigbor.first][neigbor.second] != '1')
                    continue;
                // 剔除已经加入队列的
                if (visted[neigbor.first][neigbor.second])
                    continue;
                cout << neigbor.first;
                cout << "--";
                cout << neigbor.second;
                cout << endl;
                queue.push(neigbor);
                visted[neigbor.first][neigbor.second] = true;
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        ROWCNT = grid.size();
        CLOWNCNT = grid[0].size();
        visted = vector<vector<bool>>(ROWCNT, vector<bool>(CLOWNCNT, false));
        int cnt = 0;
        for (int i = 0; i < ROWCNT; i++) {
            for (int j = 0; j < CLOWNCNT; j++) {
                if (grid[i][j] == '1' && !visted[i][j]) { // 陆地 没有遍历过
                    bfs(i, j, grid);
                    cnt++;
                    cout << cnt;
                    cout << "---count";
                    cout << endl;
                }
            }
        }
        return cnt;
    }
};

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
35
36
37
38
39
class Solution {
public:
    vector<vector<bool>> visted;
    int ROWCNT;   // 行数
    int CLOWNCNT; // 列数
    void dfs(int x, int y, vector<vector<char>>& grid) {
        visted[x][y] = true;
        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 (pair<int, int> neigbor : neigbors) {
            if (neigbor.first >= ROWCNT || neigbor.second >= CLOWNCNT ||
                neigbor.first < 0 || neigbor.second < 0) // 越界
                continue;
            if (grid[neigbor.first][neigbor.second] != '1') // 不是岛屿
                continue;
            if (visted[neigbor.first][neigbor.second]) // 访问过了
                continue;
            dfs(neigbor.first, neigbor.second,grid);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        ROWCNT = grid.size();
        CLOWNCNT = grid[0].size();
        visted = vector<vector<bool>>(ROWCNT, vector<bool>(CLOWNCNT, false));
        int cnt = 0;
        for (int i = 0; i < ROWCNT; i++) {
            for (int j = 0; j < CLOWNCNT; j++) {
                if (grid[i][j] == '1' && !visted[i][j]) { // 陆地 没有遍历过
                    dfs(i, j, grid);
                    cnt++;
                    // cout << cnt << "---count" << endl;
                }
            }
        }
        return cnt;
    }
};