题目
给你一个由 '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：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
解题
方法一：深度优先遍历DFS
类似于，找到一个岛屿上的一个点，便把这个岛屿给变消失，同时记录岛屿数量+1
python解法
class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(grid,i,j): if not 0<=i<len(grid) or not 0<=j<len(grid[0]) or grid[i][j]=='0':return grid[i][j]="0" dfs(grid, i + 1, j) dfs(grid, i, j + 1) dfs(grid, i - 1, j) dfs(grid, i, j - 1) num=0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j]=="1": dfs(grid,i,j) num+=1 return num
c++解法
class Solution { public: vector<vector<int>> dirs={{-1,0},{1,0},{0,1},{0,-1}}; int numIslands(vector<vector<char>>& grid) { int res=0; for(int i=0;i<grid.size();i++){ for(int j=0;j<grid[0].size();j++){ if(grid[i][j]=='0') continue; if(grid[i][j]=='1'){ dfs(grid,i,j); res++; } } } return res; } void dfs(vector<vector<char>>& grid,int i,int j){ if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0') return; grid[i][j]='0'; for(vector<int>& dir:dirs){ int nx=i+dir[0],ny=j+dir[1]; dfs(grid,nx,ny); } } };
方法二：广度优先遍历 BFS
class Solution: def numIslands(self, grid: [[str]]) -> int: def bfs(grid, i, j): queue = [[i, j]] while queue: [i, j] = queue.pop(0) if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1': grid[i][j] = '0' queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]] count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': bfs(grid, i, j) count += 1 return count
方法三：并查集
对于矩阵尚每个点，可以将二维的转化成一维的索引，index=i*n+j
class UnionFind{ private: vector<int> parent; int setNum; public: UnionFind(int n){ parent.resize(n); iota(parent.begin(),parent.end(),0); setNum=n; } int find(int index){ if(parent[index]==index) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ int p1=find(index1); int p2=find(index2); if(p1!=p2){ parent[p1]=p2; setNum--; } } int getSetNum(){ return setNum; } }; class Solution { public: vector<vector<int>> dirs={{-1,0},{0,-1}}; int numIslands(vector<vector<char>>& grid) { int m=grid.size(),n=grid[0].size(); UnionFind uf(n*m); int space=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='0'){ space++; continue; } for(vector<int>& dir:dirs){ int nx=i+dir[0],ny=j+dir[1]; if(nx<0||ny<0) continue; if(grid[nx][ny]=='1') uf.unite(i*n+j,nx*n+ny); } } } return uf.getSetNum()-space; } };
