【代码随想录day49】【C++复健】 99. 岛屿数量dfs；99. 岛屿数量bfs； 100. 岛屿的最大面积

99. 岛屿数量dfs

首先尝试自己想，发现自己没什么思路，毕竟这里面的东西和细节都很多，比如这个int dir[4][2]的方向数组，虽然大概也看到了要设置这么个东西，但我写了个vector，甚至已经忘了还可以设置int数组这么东西。

那如果是int数组的话，作为函数的传入值应该是什么（虽然解析里面用的是全局变量）？

答案是：函数参数为int* arr，表示指向整数的指针。

然后就是我没有体会到为什么要用dfs，我当时想的是，挨个去遍历每个陆地，然后有陆地的情况下，就使用一个专门的函数去判断其上下左右有没有其他陆地，有的话就把visited标成1。

但这么想是错的，看一眼GPT举出的反例：

代码逻辑回顾

你的代码通过以下步骤计数岛屿：

1. 遍历每个单元格：对于每个单元格 (i, j)，如果它是岛屿的一部分（即 island[i][j] == 1），则进行以下操作：

   • 如果该单元格尚未被访问过，则将岛屿数量 isnum 增加1，并将其标记为已访问。
   • 调用 check 函数，检查其四个直接邻居（上、下、左、右），并将这些邻居如果是岛屿的部分也标记为已访问。

2. 标记邻居：check 函数仅标记直接相邻的单元格为已访问，而不进行递归或进一步的检查。

代码的局限性

虽然这种方法在一些简单的情况下有效，但在处理复杂形状的岛屿时会出错。以下是具体的反例说明：

反例：多步连接的岛屿

考虑以下3x3的网格：

1 1 0
1 0 1 
0 1 1

网格表示：

[1, 1, 0]
[1, 0, 1]
[0, 1, 1]

预期结果： 2个岛屿

• 岛屿1：包含 (0,0), (0,1), (1,0)
• 岛屿2：包含 (1,2), (2,1), (2,2)

代码执行流程：

1. 处理 (0,0)：

   • isnum 增加到 1。
   • 标记 (1,0) 和 (0,1) 为已访问。

2. 处理 (0,1)：

   • 已被标记为访问过，跳过。

3. 处理 (0,2)：

   • 不是岛屿，跳过。

4. 处理 (1,0)：

   • 已被标记为访问过，跳过。

5. 处理 (1,1)：

   • 不是岛屿，跳过。

6. 处理 (1,2)：

   • isnum 增加到 2。
   • 标记 (2,2) 为已访问。

7. 处理 (2,0)：

   • 不是岛屿，跳过。

8. 处理 (2,1)：

   • isnum 增加到 3。
   • 标记 (2,2) 为已访问（已标记过）。

9. 处理 (2,2)：

   • 已被标记为访问过，跳过。

最终结果： isnum = 3，但实际应该是 2。

问题所在：

• 多步连接未被识别：虽然 (1,2) 和 (2,1) 通过 (2,2) 连接，但你的 check 函数只检查直接邻居，没有进行递归或多步的标记。这导致 (2,1) 被误认为是一个独立的岛屿。

#include<iostream>
#include<vector>
using namespace std;int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
void dfs(vector<vector<int>>& island, vector<vector<int>>& visited, int x, int y){int m = island.size();int n = island[0].size();for(int i=0; i<4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx > m-1 || nexty < 0 || nexty > n-1){continue;}else if(island[nextx][nexty] == 1 && !visited[nextx][nexty]){visited[nextx][nexty] = 1;dfs(island, visited, nextx, nexty);}}
}int main(){int n,m;cin >> n >> m;vector<vector<int>> island(m, vector<int>(n));for(int j=0; j<n; j++){for(int i=0; i<m; i++){cin >> island[i][j];}}vector<vector<int>> visited(m, vector<int>(n));int isnum = 0;for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(island[i][j] && !visited[i][j]){isnum++;visited[i][j] = 1;dfs(island, visited, i, j);}}}cout << isnum;return 0;
}

99. 岛屿数量bfs

有了dfs的写法框架之后其实相对来说就好写很多了，不过还是遇到了2个问题：

1 受了dfs的影响，在for循环的时候仍然是按i和j来写的：

for(int k=0; k<4; k++){int nextx = i + dir[k][0];int nexty = j + dir[k][1];...

但有了队列之后其实应该是输出队头元素并且按队头元素的坐标来进行位移，属于是想少了。

2 又把所有功能写一起了

本来中间意识到了应该分成不同函数的，但是后来一想还得考虑传值，突然感觉很麻烦就直接写到一起去了... 还是不能这样搞。后面一题继续用bfs写吧，然后这次把功能分开。

3 没用用pair而是用的vector，效率相对较低。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};int main(){int n,m;cin >> n >> m;vector<vector<int>> island(m, vector<int>(n));for(int j=0; j<n; j++){for(int i=0; i<m; i++){cin >> island[i][j];}}vector<vector<int>> visited(m, vector<int>(n));queue<vector<int>> qu;int num_is = 0;for(int i=0; i<m; i++){for(int j=0; j<n; j++){while(!qu.empty()){vector<int> front = qu.front();qu.pop();for(int k=0; k<4; k++){int nextx = front[0] + dir[k][0];int nexty = front[1] + dir[k][1];if(nextx <0 || nextx > m-1 || nexty <0 || nexty >n-1){continue;}else if(island[nextx][nexty] && !visited[nextx][nexty]){visited[nextx][nexty] = 1;qu.push({nextx, nexty});}}}if(island[i][j] && !visited[i][j] && qu.empty()){num_is++;qu.push({i, j});visited[i][j] = 1;}}}cout << num_is;return 0;
}

 100. 岛屿的最大面积

基本上问题不大，除了试图将island[nextx][nexty]塞进一个pair（明明应该塞两个坐标，我把值塞进去干什么？），以及pair的访问方式是.first和.second，而非下标方式访问。只能说我的悟性还是可以的嘛！

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};int bfs(vector<vector<bool>>& visited, vector<vector<int>>& island, queue<pair<int, int>>& qu){int area = 0;int m = island.size();int n = island[0].size();while(!qu.empty()){pair<int, int> cur = qu.front();qu.pop();area++;for(int i=0 ;i<4; i++){int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if(nextx < 0 || nextx > m-1 || nexty <0 || nexty >n-1){continue;}else if(island[nextx][nexty] && !visited[nextx][nexty]){qu.push({nextx, nexty});visited[nextx][nexty] = true;}}}return area;
}int main(){int n, m;cin >> n >> m;vector<vector<int>> island(m, vector<int>(n));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin >> island[j][i];}}vector<vector<bool>> visited(m, vector<bool>(n));queue<pair<int, int>> qu;int maxarea = 0;for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(island[i][j] && !visited[i][j] && qu.empty()){qu.push({i, j});visited[i][j] = true;int area = bfs(visited, island, qu);maxarea = max(maxarea, area);}}}cout << maxarea;
}