代码随想录算法训练营 Day51 图论Ⅱ岛屿题目Ⅰ

图论

题目

99. 岛屿数量
使用 DFS 实现方法
判断岛屿方法
1. 遍历图，若遍历到了陆地 grid[j] = 1 而且陆地没有被访问，在这个陆地的基础上进行 DFS 方法，大概是 BFS 方法
2. 对陆地进行 DFS 的时间时刻注意以访问的元素添加访问标记

1. // DFS方法1
2. #include <iostream>
3. #include <vector>
5. int dir[4][2] = {0,1,1,0,-1,0,0,-1};
6. void dfs(std::vector<std::vector<int>>& grid, std::vector<std::vector<bool>>& vis, int x, int y) {
7.     // 从四个方向进行搜索
8.     for (int i = 0; i < 4; ++i) {
9.         int nexti = x + dir[i][0];
10.         int nextj = y + dir[i][1];
11.         // 边界情况判定
12.         if (nexti < 0 || nexti >= grid.size()
13.          || nextj < 0 || nextj >= grid[0].size()) continue;
14.         // 访问情况判定
15.         if (!vis[nexti][nextj] && grid[nexti][nextj] == 1) {
16.             // 时刻注意访问标记
17.             vis[nexti][nextj] = true;
18.             dfs(grid, vis, nexti, nextj);
19.         }
20.     }
21. }
23. int main() {
24.     // 输入处理
25.     int n, m, res = 0;
26.     std::cin >> n >> m;
27.     std::vector<std::vector<int>> grid(n, std::vector<int>(m, 0));
28.     std::vector<std::vector<bool>> vis(n, std::vector<bool>(m, false));
29.     for (int i = 0; i < n; ++i) {
30.         for (int j = 0; j < m; ++j) {
31.             std::cin >> grid[i][j];
32.         }
33.     }
34.     // 遍历网格进行DFS操作
35.     for (int i = 0; i < n; ++i) {
36.         for (int j = 0; j < m; ++j) {
37.             // 访问到新陆地对该陆地进行遍历
38.             if (grid[i][j] == 1 && !vis[i][j]) {
39.                 res++; // 记录新大陆
40.                 vis[i][j] = true;
41.                 dfs(grid, vis, i, j);
42.             }
43.         }
44.     }
46.     // 输出处理
47.     std::cout << res << std::endl;
48. }
51. // dfs 三部曲写法
52. #include <iostream>
53. #include <vector>
54. using namespace std;
56. int dir[4][2] = {0,-1,-1,0,1,0,0,1}; // 逆时针顺序
57. // 第一步参数与返回值
58. void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
59.     // 第二部 终止条件
60.     if (vis[x][y] || grid[x][y] == 0) return;
61.     // 第三部 单层递归逻辑
62.     vis[x][y] = true;
63.     for (int i = 0; i < 4; ++i) {
64.         int nextX = x + dir[i][0];
65.         int nextY = y + dir[i][1];
66.         if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
67.         dfs(grid, vis, nextX, nextY);
68.     }
69. }
71. int main() {
72.     int n, m, res = 0;
73.     cin >> n >> m;
74.     vector<vector<int>> grid(n, vector<int>(m, 0));
75.     vector<vector<bool>> vis(n, vector<bool>(m, false));
76.     for (int i = 0; i < n; ++i) {
77.         for (int j = 0; j < m; ++j) {
78.             cin >> grid[i][j];
79.         }
80.     }
82.     for (int i = 0; i < n; ++i) {
83.         for (int j = 0; j < m; ++j) {
84.             if (!vis[i][j] && grid[i][j] == 1) {
85.                 res++;
86.                 dfs(grid, vis, i, j);
87.             }
88.         }
89.     }
91.     cout << res << endl;
92. }

复制代码

使用广度优先搜刮方法
主函数部分稳固，调用酿成广度优先搜刮
广度优先搜刮包管入队列的时间就对数据做标记为访问
如果在取出队列时间标记会导致大量重复元素入队！

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. using namespace std;
6. int dir[4][2] = {0,-1,-1,0,1,0,0,1};
7. void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
8.     // 创建队列存储下标
9.     queue<pair<int, int>> que;
10.     // 保证入队的时候就标记访问防止重复访问
11.     que.push(make_pair(x, y));
12.     while (!que.empty()) {
13.         pair<int, int> cur = que.front();
14.         que.pop();
15.         for (int i = 0; i < 4; ++i) {
16.             int nextX = cur.first + dir[i][0];
17.             int nextY = cur.second + dir[i][1];
18.             if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
19.             if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
20.                 que.push({nextX, nextY});
21.                 vis[nextX][nextY] = true; // 入队即标记防止重复
22.             }
23.         }
24.     }
25. }
27. int main() {
28.     int n, m, res = 0;
29.     cin >> n >> m;
30.     vector<vector<int>> grid(n, vector<int>(m, 0));
31.     vector<vector<bool>> vis(n, vector<bool>(m, false));
32.     for (int i = 0; i < n; ++i) {
33.         for (int j = 0; j < m; ++j) {
34.             cin >> grid[i][j];
35.         }
36.     }
38.     for (int i = 0; i < n; ++i) {
39.         for (int j = 0; j < m; ++j) {
40.             if (!vis[i][j] && grid[i][j] == 1) {
41.                 res++;
42.                 bfs(grid, vis, i, j);
43.             }
44.         }
45.     }
47.     cout << res << endl;
48. }

复制代码

100. 岛屿的最大面积
岛屿最大面积，给出广度优先搜刮，深度优先搜刮（A 和 B）
深度优先 B广度优先在函数外初始化记录，深度优先 A 在函数内初始化记录

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <algorithm>
5. using namespace std;
7. int tmp = 0;
8. int dir[4][2] = {0,-1,-1,0,1,0,0,1};
10. int bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
11.     tmp = 1;
12.     queue<pair<int, int>> que;
13.     que.push(make_pair(x, y));
14.     vis[x][y] = true;
15.     while (!que.empty()) {
16.         pair<int, int> cur = que.front();
17.         que.pop();
18.         for (int i = 0; i < 4; ++i) {
19.             int nextX = cur.first + dir[i][0];
20.             int nextY = cur.second + dir[i][1];
21.             if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
22.             if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
23.                 tmp++;
24.                 que.push({nextX, nextY});
25.                 vis[nextX][nextY] = true;
26.             }
27.         }
28.     }
29.     return tmp;
30. }
32. void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
33.     // 1 fin
34.     if (vis[x][y] || grid[x][y] == 0) return;
35.     vis[x][y] = true;
36.     tmp++;
37.     for (int i = 0; i < 4; ++i) {
38.         int nextX = x + dir[i][0];
39.         int nextY = y + dir[i][1];
40.         if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
41.         dfs(grid, vis, nextX, nextY);
42.     }
43. }
45. void dfs2(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
46.     // 2
47.     for (int i = 0; i < 4; ++i) {
48.         int nextX = x + dir[i][0];
49.         int nextY = y + dir[i][1];
50.         if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY > grid[0].size()) continue;
51.         if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
52.             tmp++;
53.             vis[nextX][nextY] = true;
54.             dfs2(grid, vis, nextX, nextY);
55.         }
56.     }
57. }
60. int main(){
61.     int n, m, res = 0, maxV = 0;
62.     cin >> n >> m;
63.     vector<vector<int>> grid(n, vector<int>(m, 0));
64.     vector<vector<bool>> vis(n, vector<bool>(m, false));
65.     for (int i = 0; i < n; ++i) {
66.         for (int j = 0; j < m; ++j) {
67.             cin >> grid[i][j];
68.         }
69.     }
71.     for (int i = 0; i < n; ++i) {
72.         for (int j = 0; j < m; ++j) {
73.             if (!vis[i][j] && grid[i][j] == 1) {
74.                 res++;
75.                 // 深度优先 1
76.                 // tmp = 0; // 因为dfs内首先计算tmp
77.                 // dfs(grid, vis, i, j);
78.                 // maxV = max(maxV, tmp);
79.                 // 深度优先 2
80.                 tmp = 1; // dfs需要初始
81.                 vis[i][j] = true;
82.                 dfs2(grid, vis, i, j);
83.                 maxV = max(maxV, tmp);
84.                 // 广度优先
85.                 // maxV = max(maxV, bfs(grid, vis, i, j));
86.             }
87.         }
88.     }
89.     // cout << "res" << res << endl;
90.     cout << maxV << endl;
91.     return 0;
92. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。