文章目录
-
-
-
- 【99.计数孤岛】
* * DFS版本
* BFS版本
* 【100.岛屿的最大面积】
* * DFS写法
* BFS写法
- 【99.计数孤岛】
-
-
【99.计数孤岛】
思路:
用遇到一个没有遍历过的节点陆地,计数器就加一,然后把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
DFS版本
1# include <iostream> 2# include <vector> 3 4using namespace std; 5 6int dir[4][2] = {0,1,1,0,0,-1,-1,0}; // 四个方向 7void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ 8 for(int i = 0; i < 4; i++){ 9 int nextx = x + dir[i][0]; 10 int nexty = y + dir[i][1]; 11 if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; 12 // 越界了直接跳过 13 if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){ 14 15 visited[nextx][nexty] = true; 16 dfs(grid, visited, nextx, nexty); 17 } 18 } 19} 20 21int main(){ 22 int n, m; 23 cin >> n >> m; 24 vector<vector<int>> grid(n, vector<int>(m, 0)); 25 vector<vector<bool>> visited(n, vector<bool>(m, false)); 26 27 for(int i = 0; i < n; i++){ 28 for(int j = 0; j < m; j++){ 29 cin >> grid[i][j]; 30 } 31 } 32 33 int result = 0; 34 for(int i = 0; i < n; i++){ 35 for(int j = 0; j < m; j++){ 36 if(!visited[i][j] && grid[i][j] == 1){ 37 visited[i][j] = true; 38 result ++; 39 dfs(grid, visited, i, j); 40 } 41 } 42 } 43 44 cout << result << endl; 45 return 0; 46} 47
BFS版本
这里有一个广搜中很重要的细节:
根本原因是只要 加入队列就代表 走过,就需要标记,而不是从队列拿出来的时候再去标记走过。
区别在哪里?
如果从队列拿出节点,再去标记这个节点走过,就会发生下图所示的结果,会导致很多节点重复加入队列。

超时写法 (从队列中取出节点再标记,注意代码注释的地方)
1int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向 2void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { 3 queue<pair<int, int>> que; 4 que.push({x, y}); 5 while(!que.empty()) { 6 pair<int ,int> cur = que.front(); que.pop(); 7 int curx = cur.first; 8 int cury = cur.second; 9 visited[curx][cury] = true; // 从队列中取出在标记走过 10 for (int i = 0; i < 4; i++) { 11 int nextx = curx + dir[i][0]; 12 int nexty = cury + dir[i][1]; 13 if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了,直接跳过 14 if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { 15 que.push({nextx, nexty}); 16 } 17 } 18 } 19 20} 21
加入队列 就代表走过,立刻标记,正确写法: (注意代码注释的地方)
1int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向 2void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { 3 queue<pair<int, int>> que; 4 que.push({x, y}); 5 visited[x][y] = true; // 只要加入队列,立刻标记 6 while(!que.empty()) { 7 pair<int ,int> cur = que.front(); que.pop(); 8 int curx = cur.first; 9 int cury = cur.second; 10 for (int i = 0; i < 4; i++) { 11 int nextx = curx + dir[i][0]; 12 int nexty = cury + dir[i][1]; 13 if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了,直接跳过 14 if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { 15 que.push({nextx, nexty}); 16 visited[nextx][nexty] = true; // 只要加入队列立刻标记 17 } 18 } 19 } 20 21} 22
以上两个版本其实,其实只有细微区别,就是 visited[x][y] = true; 放在的地方,这取决于我们对 代码中队列的定义,队列中的节点就表示已经走过的节点。 所以只要加入队列,立即标记该节点走过。
1# include <iostream> 2# include <vector> 3# include <queue> 4 5using namespace std; 6 7int dir[4][2] = {0,1,1,0,0,-1,-1,0}; // 四个方向 8void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ 9 queue<pair<int, int>> que; 10 que.push({x, y}); 11 visited[x][y] = true; // 只要加入队列,立即做标记 12 while(!que.empty()){ 13 pair<int, int> cur = que.front(); que.pop(); 14 int curx = cur.first; 15 int cury = cur.second; 16 for(int i = 0; i < 4; i++){ 17 int nextx = curx + dir[i][0]; 18 int nexty = cury + dir[i][1]; 19 if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; 20 if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){ 21 que.push({nextx, nexty}); 22 visited[nextx][nexty] = true; // 只要加入队列,立即做标记 23 } 24 } 25 } 26} 27 28int main(){ 29 int n, m; 30 cin >> n >> m; 31 vector<vector<int>> grid(n, vector<int>(m, 0)); 32 vector<vector<bool>> visited(n, vector<bool>(m, false)); 33 34 for(int i = 0; i < n; i++){ 35 for(int j = 0; j < m; j++){ 36 cin >> grid[i][j]; 37 } 38 } 39 40 int result = 0; 41 for(int i = 0; i < n; i++){ 42 for(int j = 0; j < m; j++){ 43 if(!visited[i][j] && grid[i][j] == 1){ 44 result++; 45 bfs(grid, visited, i, j); 46 } 47 } 48 } 49 50 cout << result << endl; 51 return 0; 52} 53
【100.岛屿的最大面积】
DFS写法
1# include <iostream> 2# include <vector> 3 4using namespace std; 5 6int count = 0; 7int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; 8void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ 9 for(int i = 0; i < 4; i++){ 10 int nextx = x + dir[i][0]; 11 int nexty = y + dir[i][1]; 12 if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; 13 if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){ 14 15 visited[nextx][nexty] = true; 16 count ++; 17 dfs(grid, visited, nextx, nexty); 18 } 19 } 20} 21 22int main(){ 23 int n, m; 24 cin >> n >> m; 25 vector<vector<int>> grid(n, vector<int>(m, 0)); 26 vector<vector<bool>> visited(n, vector<bool>(m, false)); 27 28 for(int i = 0; i < n; i++){ 29 for(int j = 0; j < m; j++){ 30 cin >> grid[i][j]; 31 } 32 } 33 int result = 0; 34 for(int i = 0; i < n; i++){ 35 for(int j = 0; j < m; j++){ 36 if(!visited[i][j] && grid[i][j] == 1){ 37 visited[i][j] = true; 38 count = 1; 39 dfs(grid, visited, i, j); 40 result = max(result, count); 41 } 42 } 43 } 44 cout << result << endl; 45 return 0; 46} 47
BFS写法
1# include <iostream> 2# include <vector> 3# include <queue> 4 5using namespace std; 6 7int count = 0; 8int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; 9void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){ 10 queue<pair<int, int>> que; 11 que.push({x, y}); 12 visited[x][y] = true; 13 count++; 14 while(!que.empty()){ 15 pair<int, int> cur = que.front(); que.pop(); 16 int curx = cur.first; 17 int cury = cur.second; 18 for(int i = 0; i < 4; i++){ 19 int nextx = curx + dir[i][0]; 20 int nexty = cury + dir[i][1]; 21 if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; 22 if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){ 23 que.push({nextx, nexty}); 24 visited[nextx][nexty] = true; 25 count++; 26 } 27 } 28 } 29} 30 31int main(){ 32 int n, m; 33 cin >> n >> m; 34 vector<vector<int>> grid(n, vector<int>(m, 0)); 35 vector<vector<bool>> visited(n, vector<bool>(m, false)); 36 37 for(int i = 0; i < n; i++){ 38 for(int j = 0; j < m; j++){ 39 cin >> grid[i][j]; 40 } 41 } 42 int result = 0; 43 for(int i = 0; i < n; i++){ 44 for(int j = 0; j < m; j++){ 45 if(!visited[i][j] && grid[i][j] == 1){ 46 count = 0; 47 bfs(grid, visited, i, j); 48 result = max(result, count); 49 } 50 } 51 } 52 cout << result << endl; 53 return 0; 54} 55
《《代码随想录》刷题打卡day44:图论-part02》 是转载文章,点击查看原文。
