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':
continue
else:
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=0
for 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+=1
return cntbfs思路：
与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=0
m=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':
continue
else:
cnt+=1
q.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':
continue
else:
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':
continue
else:
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;}
}
}
//Union
for(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 x
Father[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 cnt
Father[Fy]=Fx
cnt-=1
return cnt
def 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=0
for i in range(m):
for j in range(n):
temp=n*i+j
if grid[i][j]=='1':
Father[temp]=temp
cnt+=1
else:
Father[temp]=-1
for i in range(m):
for j in range(n):
if grid[i][j]=='0':
continue
for 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':
continue
else:
a=i*n+j
b=x*n+y
cnt=self.Union(Father,a,b,cnt)
return cnt
注意类中函数第一个参数为self
![[MYSQL数据库]--表的增删查改和字段类型](https://img-blog.csdnimg.cn/direct/fa52ac85a8f8464db0768496d77c5877.png)
