LeetCode刷题（80）～岛屿数量【DFS+BFS 并查集未懂！】

题目描述

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

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

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

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

解答 By 海轰

提交代码（DFS）

void dfs(vector<vector<char>>& grid,int r,int c) { // 越界处理 if(!(0<=r&&r<grid.size()&&0<=c&&c<grid[0].size())) return ; // 不是陆地 if(grid[r][c]!='1') return ; grid[r][c]='2';// 将遍历过的地方更新为 防止循环 dfs(grid,r-1,c); dfs(grid,r+1,c); dfs(grid,r,c+1); dfs(grid,r,c-1); } int numIslands(vector<vector<char>>& grid) { int count=0; for(int i=0;i<grid.size();++i) { for(int j=0;j<grid[0].size();++j) { if(grid[i][j]=='1') { dfs(grid,i,j); ++count; } } } return count; }

  

 

  
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
 

运行结果

提交代码（BFS）

int numIslands(vector<vector<char>>& grid) { int nr = grid.size(); if (!nr) return 0; int nc = grid[0].size(); int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; queue<pair<int, int>> neighbors; neighbors.push({r, c}); while (!neighbors.empty()) { auto rc = neighbors.front(); neighbors.pop(); int row = rc.first, col = rc.second; if (row - 1 >= 0 && grid[row-1][col] == '1') { neighbors.push({row-1, col}); grid[row-1][col] = '0'; } if (row + 1 < nr && grid[row+1][col] == '1') { neighbors.push({row+1, col}); grid[row+1][col] = '0'; } if (col - 1 >= 0 && grid[row][col-1] == '1') { neighbors.push({row, col-1}); grid[row][col-1] = '0'; } if (col + 1 < nc && grid[row][col+1] == '1') { neighbors.push({row, col+1}); grid[row][col+1] = '0'; } } } } } return num_islands; }

  

 

  
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
 

运行结果

解答

• DFS+BFS+并查集

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108131996