力扣hot---岛屿数量

dfs思路：

首先通过两层for循环遍历每一个点，如果这个点为0或者2（这个2是什么呢？是在遍历该点以及该点连成的这一片区域中，因为通过深度优先搜索，遍历该点就等于遍历这一片区域，遍历这篇区域中的点的同时，将这些元素标记为2，即代表这篇区域已经遍历过），那么遍历下一个点。遇到一个新的区域则cnt++。

那么怎么进行深度搜索呢？即如果该点=1，那么将该点的上方、下方、左方、右方送入dfs。

dfs代码：

C++:

class Solution {
public:int p_m[4]={-1,1,0,0};int p_n[4]={0,0,-1,1};void dfs(vector<vector<char>>& grid,int i,int j,int m,int n){for(int k=0;k<4;k++){int x=i+p_m[k];int y=j+p_n[k];if(x>=0 && x<m && y>=0 && y<n){if(grid[x][y]=='0'||grid[x][y]=='2'){continue;}else{grid[x][y]='2';dfs(grid,x,y,m,n);}}}}int numIslands(vector<vector<char>>& grid) {int m=grid.size();int n=grid[0].size();//cout<<m<<' '<<n<<endl;int cnt=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='2'||grid[i][j]=='0'){continue;}else{dfs(grid,i,j,m,n);cnt++;}}}return cnt;}
};

注意：二维数组中，求行数为 

int m=grid.size();

求列数为

int n=grid[0].size();

python：

class Solution:def dfs(self,grid:List[list[str]],i:int,j:int,m:int,n:int) -> int:p_m=[-1,1,0,0]p_n=[0,0,-1,1]for k in range(4):x=i+p_m[k]y=j+p_n[k]if x>=0 and x<m and y>=0 and y<n:if grid[x][y]=='0' or grid[x][y]=='2':continueelse:grid[x][y]='2'self.dfs(grid,x,y,m,n)def numIslands(self, grid: List[List[str]]) -> int:m=len(grid)n=len(grid[0])cnt=0for i in range(m):for j in range(n):if grid[i][j]=='2' or grid[i][j]=='0':continue;else:self.dfs(grid,i,j,m,n)cnt+=1return cnt

bfs思路：

与dfs类似，遍历每个元素时，如果该元素的值为1，那么将其入队列，并且考虑其上下左右的元素，如果周围元素值为1，将其也入队列。遍历一个元素时，如果该值为1，那么代表访问了一个新的区域，则cnt++。

代码：

C++：

class Solution {
public:deque<pair<int,int>> q;int p_x[4]={-1,1,0,0};int p_y[4]={0,0,1,-1};int numIslands(vector<vector<char>>& grid) {int cnt=0;int m=grid.size();int n=grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='0'||grid[i][j]=='2'){continue;}else{cnt++;}q.push_back({i,j});while(!q.empty()){pair<int,int> temp=q.front();q.pop_front();int temp_x=temp.first;int temp_y=temp.second;if(grid[temp_x][temp_y]=='0'||grid[temp_x][temp_y]=='2'){continue;}else{grid[temp_x][temp_y]='2';for(int k=0;k<4;k++){int x=temp_x+p_x[k];int y=temp_y+p_y[k];if(x>=0 && x<m && y>=0 && y<n){if(grid[x][y]=='0'||grid[x][y]=='2'){continue;}else{q.push_back({x,y});}}}}}}}return cnt;}
};

明显可以看到bfs要比dfs慢的多。

 python：

class Solution:def numIslands(self, grid: List[List[str]]) -> int:q=deque()p_x=[-1,1,0,0]p_y=[0,0,1,-1]cnt=0m=len(grid)n=len(grid[0])for i in range(m):for j in range(n):if grid[i][j]=='0' or grid[i][j]=='2':continueelse:cnt+=1q.append((i,j))while q:temp=q[0]q.popleft()temp_x=temp[0]temp_y=temp[1]if grid[temp_x][temp_y]=='0' or grid[temp_x][temp_y]=='2':continueelse:grid[temp_x][temp_y]='2'for k in range(4):x=temp_x+p_x[k]y=temp_y+p_y[k]if x>=0 and x<m and y>=0 and y<n:if grid[x][y]=='0' or grid[x][y]=='2':continueelse:q.append((x,y))return cnt

注意：C++中的pair<int,int>用python中的tuple来代替

q.append((i,j))

同时，记得添加from collections import deque 

并查集思路：

遍历所有元素，如果该元素为‘0’，则跳过；如果该元素为‘1’，cnt++（岛屿数++，后面再依次向下减），同时为其分配一个Father结点，值为其本身，但是本身是（i,j），该怎么存到Father数组中呢？用二维数组转换成一维数组的方法，即将（i,j）转换为（i*n+j）【相当于以行优先，看是第几个元素】。接下来，依次判断上下左右值，如果为1，就和自己合并。这里分为真合并和假合并，假合并就是这两个值原来就合并过。如果是真合并，则进行cnt--的操作。

并查集代码：

C++：

class Solution {
public:int p_x[4]={-1,1,0,0};int p_y[4]={0,0,-1,1};int cnt=0;int find(vector<int>& Father,int x){if(Father[x]==x){return x;}Father[x]=find(Father,Father[x]);return Father[x];}void Union(vector<int>& Father,int x,int y){int Fx=find(Father,x);int Fy=find(Father,y);if(Fx==Fy){return;}Father[Fy]=Fx;cnt--;}int numIslands(vector<vector<char>>& grid) {int m=grid.size();int n=grid[0].size();vector<int> Father(m*n,0);//初始化Father数组for(int i=0;i<m;i++){for(int j=0;j<n;j++){int temp=n*i+j;if(grid[i][j]=='1'){Father[temp]=temp;cnt++;}else{Father[temp]=-1;}}}//Unionfor(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='0'){continue;}for(int k=0;k<4;k++){int x=i+p_x[k];int y=j+p_y[k];if(x>=0 && x<m && y>=0 && y<n){if(grid[x][y]=='0'){continue;}else{int a=i*n+j;int b=x*n+y;Union(Father,a,b);}}}}}return cnt;}
};

Python：

 

class Solution:def find(self,Father:List[int],x:int) -> int:if Father[x]==x:return xFather[x]=self.find(Father,Father[x])return Father[x]def Union(self,Father:List[int],x:int,y:int,cnt:int) ->int:Fx=self.find(Father,x)Fy=self.find(Father,y)if Fx==Fy:return cntFather[Fy]=Fxcnt-=1return cntdef numIslands(self, grid: List[List[str]]) -> int:p_x=[-1,1,0,0]p_y=[0,0,-1,1]m=len(grid)n=len(grid[0])Father=[0]*(m*n)cnt=0for i in range(m):for j in range(n):temp=n*i+jif grid[i][j]=='1':Father[temp]=tempcnt+=1else:Father[temp]=-1for i in range(m):for j in range(n):if grid[i][j]=='0':continuefor k in range(4):x=i+p_x[k]y=j+p_y[k]if x>=0 and x<m and y>=0 and y<n:if grid[x][y]=='0':continueelse:a=i*n+jb=x*n+ycnt=self.Union(Father,a,b,cnt)return cnt

注意类中函数第一个参数为self