【Leetcode】200. 岛屿数量

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

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

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

示例 1：

输入：

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
1
2
3
4
5
6

输出：1

示例 2：

输入：

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
1
2
3
4
5
6

输出：3

提示：

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

---

AC:

/*
 * @lc app=leetcode.cn id=200 lang=cpp
 *
 * [200] 岛屿数量
 */

// @lc code=start
class Solution {
private:
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<pair<int, int>> que;
        que.push({x, y});
        visited[x][y] = true;
        while(!que.empty()) {
            pair<int, int> cur = que.front();
            que.pop();
            int curX = cur.first;
            int curY = cur.second;
            for(int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];
                if(nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) {
                    continue;
                }
                if(!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                    que.push({nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid[0].size(), n = grid.size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && grid[i][j] == '1') {
                    count++;
                    bfs(grid, visited, i, j);
                }
            }
        }
        return count;
    }
};
// @lc code=end
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

---

相比较之 DFS 递归式写法
BFS 更多的感觉是在于 栈，队列，数组这类数据结构的使用，
就纯粹的的 BFS 问题而言，个人觉得使用队列（先进先出）存储坐标会比较好点，其中坐标可以是用 pair 函数定义存储。

---

BFS（广度优先搜索）C++模板：

#include 
#include 
using namespace std;

const int N = 100010;
int n;  // 图中结点个数
vector<int> g[N];  // 存储图

void bfs(int u)  // u为起点
{
    queue<int> q;
    q.push(u);  // 入队

    bool st[N] = {};  // 标记是否访问过
    st[u] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        // 处理结点t
        cout << t << " ";

        // 将t的所有邻接点加入队列
        for (auto v : g[t])
            if (!st[v])
            {
                q.push(v);
                st[v] = true;
            }
    }
}

int main()
{
    cin >> n;

    int m;
    cin >> m;  // m是图中边的个数

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bfs(1);  // 以1为起点进行BFS

    return 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
45
46
47
48
49
50
51
52
53

DFS（深度优先搜索）C++模板：

#include 
#include 
using namespace std;

const int N = 100010;
int n;  // 图中结点个数
vector<int> g[N];  // 存储图

void dfs(int u)
{
    // 处理结点u

    // 标记已访问过
    bool st[N] = {};
    st[u] = true;

    for (auto v : g[u])
        if (!st[v])
            dfs(v);
}

int main()
{
    cin >> n;

    int m;
    cin >> m;  // m是图中边的个数

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1);  // 以1为起点进行DFS

    return 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