title: DFS算法秒杀五道岛屿问题
top: false
cover: false
toc: true
mathjax: true
date: 2021-10-18 17:43:22
password:
summary:
tags: labuladong
categories: LeetCode
岛屿问题合集
200. 岛屿数量
利用dfs深度优先搜索解决：
- 心里先想象出一棵搜索树
- 在节点处判断：
- 如果满足条件（即：该节点没有超过二维数组范围且是岛屿（用1表示）），则把该点置为水（用0表示,表示淹没该节点）以避免重复搜索。并在此节点的基础上，继续向搜索树下面（下面的选择有上下左右四个分支）搜索
- 若不满足条件，则返回
- 一开始时，搜索树的入口：grid[i][j]处若为1，则进入搜索树。用count来计数，每进入一次树，count+=1
- 递归函数
dfs()的功能：找到一块陆地，并以这块陆地为中心（先淹没当前陆地），然后尽可能地淹没它周围的陆地
class Solution:
def numIslands(self, grid):
def dfs(grid, i, j):
# grid[i][j] 点若是岛屿，则把该点置0，避免后续重复搜索到。然后从该点的上下左右继续搜
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
grid[i][j] = '0'
# 淹没周围陆地
dfs(grid, i + 1, j)
dfs(grid, i, j + 1)
dfs(grid, i - 1, j)
dfs(grid, i, j - 1)
else:
return
count = 0 # 每进入一次搜索树，cont+=1
for i in range(len(grid)):
for j in range(len(grid[0])):
# 搜索树的入口
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return countclass Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地
void dfs(int i, int j, vector<vector<char>> &grid) {
int m = grid.size();
int n = grid[0].size();
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1') {
grid[i][j] = '0'; // 找到当前陆地，并淹没
// 以当前节点为中心，继续淹没周围陆地
dfs(i, j + 1, grid); // 上
dfs(i, j - 1, grid);// 下
dfs(i - 1, j, grid);// 左
dfs(i + 1, j, grid);// 右
} else // 相当于递归结束的条件
return;
}
int numIslands(vector<vector<char>> &grid) {
int count = 0;
int m = grid.size();
int n = grid[0].size();
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并把count+1
if (grid[i][j] == '1') {
dfs(i, j, grid);
count++;
}
}
}
return count;
}
};1254. 统计封闭岛屿的数目
上题求岛屿的数量，也就是说，靠边的岛屿也算。而本题求封闭岛屿的数量，这时靠边的岛屿不算数。所以需在要上题的基础上，把靠边的岛屿排除掉（即淹没掉）
与上一题不同的是，本题：
- 0为陆地，1为水域，二维数组中保存的是int类型
- 先把靠边的岛屿淹没掉，然后进行for循环遍历
// 先淹没四条边上的岛屿，因为四周的岛屿不算数
for (int i = 0; i < m; ++i) {
dfs(i,0 ,grid); // 淹没第0列相关的岛屿
dfs(i,n-1 ,grid); // 淹没最后一列相关的岛屿
}
for (int j = 0; j < n; ++j) {
dfs(0,j,grid); // 淹没第一行相关的岛屿
dfs(m-1,j,grid);// 淹没最后一行相关的岛屿
}
class Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地
void dfs(int i, int j, vector<vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 0) {
grid[i][j] = 1; // 找到当前陆地，并淹没
// 以当前节点为中心，继续淹没周围陆地
dfs(i, j + 1, grid); // 上
dfs(i, j - 1, grid);// 下
dfs(i - 1, j, grid);// 左
dfs(i + 1, j, grid);// 右
} else // 相当于递归结束的条件
return;
}
int closedIsland(vector<vector<int>> &grid) {
int count = 0;
int m = grid.size();
int n = grid[0].size();
// 先淹没四条边上的岛屿，因为四周的岛屿不算数
for (int i = 0; i < m; ++i) {
dfs(i,0 ,grid); // 淹没第0列相关的岛屿
dfs(i,n-1 ,grid); // 淹没最后一列相关的岛屿
}
for (int j = 0; j < n; ++j) {
dfs(0,j,grid); // 淹没第一行相关的岛屿
dfs(m-1,j,grid);// 淹没最后一行相关的岛屿
}
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并把count+1
if (grid[i][j] == 0) {
dfs(i, j, grid);
count++;
}
}
}
return count;
}
};1020. 飞地的数量
与上一题类似的是，本题同样需要淹没四周的岛屿。本题统计封闭岛屿的面积
与上一题不同的是，本题
- 0为水域，1为陆地
- 淹没四周的岛屿后，本题不再淹没里面的岛屿，而是统计它的面积
所以在主函数签名中，当遍历整个陆地时，把上一题的
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并把count+1
if (grid[i][j] == 0) {
dfs(i, j, grid);
count++;
}
}
}改为
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则统计面积，即把count+1
if (grid[i][j] == 1) {
count++; // 不再淹没陆地，而是统计陆地的面积
}
}
}class Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地
void dfs(int i, int j, vector <vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
grid[i][j] = 0; // 找到当前陆地，并淹没
// 以当前节点为中心，继续淹没周围陆地
dfs(i, j + 1, grid); // 上
dfs(i, j - 1, grid);// 下
dfs(i - 1, j, grid);// 左
dfs(i + 1, j, grid);// 右
} else // 相当于递归结束的条件
return;
}
int numEnclaves(vector <vector<int>> &grid) {
int count = 0;
int m = grid.size();
int n = grid[0].size();
// 先淹没四周的岛屿，因为四周的岛屿不算数
for (int i = 0; i < m; ++i) {
dfs(i, 0, grid); // 淹没第0列相关的岛屿
dfs(i, n - 1, grid); // 淹没最后一列相关的岛屿
}
for (int j = 0; j < n; ++j) {
dfs(0, j, grid); // 淹没第一行相关的岛屿
dfs(m - 1, j, grid);// 淹没最后一行相关的岛屿
}
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并把count+1
if (grid[i][j] == 1) {
count++;
}
}
}
return count;
}
};
695. 岛屿的最大面积
本题计算岛屿的最大面积，则改写dfs函数即可。dfs函数不仅有淹没的功能，而且加上新的功能：在淹没过程中统计淹没的面积（给dfs函数设置返回值，记录每次淹没的陆地的个数）。
在主函数签名中，更新最大值即可。
class Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地.同时统计淹没的面积
int dfs(int i, int j, vector <vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
int tmp=0; // 记录此次淹没过程中，一共淹没的面积
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
tmp+=1; // 当前是陆地，计数+1
grid[i][j] = 0; // 找到当前陆地，并淹没
// 以当前节点为中心，继续淹没周围陆地，并把淹没的面积统计起来
int u=dfs(i, j + 1, grid); // 上
int d=dfs(i, j - 1, grid);// 下
int l=dfs(i - 1, j, grid);// 左
int r=dfs(i + 1, j, grid);// 右
return tmp+=(u+d+l+r); // 返回此次总的淹没面积
} else // 相当于递归结束的条件
return 0;
}
int maxAreaOfIsland(vector <vector<int>> &grid) {
int maxVal=0; // 保存最大值
int m = grid.size();
int n = grid[0].size();
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并用dfs(i, j, grid)得到当前淹没的面积
if (grid[i][j] == 1) {
maxVal=max(maxVal,dfs(i, j, grid)); // 更新最大值
}
}
}
return maxVal;
}
};1905. 统计子岛屿
grid1表示为A ，grid2表示为B，则类别对应关系为
B岛
- A岛
- A水
B水
- A岛
- A水
- 先淹没不符合题意的B中的岛屿小格子
本题要求被grid1完全包含的grid2中的子岛屿数。对于B中任何一个网格，
- 若B格是水，则不管A格是什么，都没必要淹没B格，保留原样即可
- 若B格是岛
- 若A格是岛，则也不需进行任何操作，保留原样即可
- 若A格是水，则需要以B格为中心，淹没掉它周围的岛屿
- 然后统计B中子岛屿个数，边统计边淹没
class Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地
void dfs(int i, int j, vector <vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
grid[i][j] = 0; // 找到当前陆地，并淹没
// 以当前节点为中心，继续淹没周围陆地，并把淹没的面积统计起来
dfs(i, j + 1, grid); // 上
dfs(i, j - 1, grid);// 下
dfs(i - 1, j, grid);// 左
dfs(i + 1, j, grid);// 右
}
}
int countSubIslands(vector <vector<int>> &grid1, vector <vector<int>> &grid2) {
int m = grid2.size();
int n = grid2[0].size();
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 若grid1中为水，grid2中为陆地，则淹没grid2中的这部分
if (grid1[i][j]==0&&grid2[i][j] == 1) {
dfs(i,j,grid2);
}
}
}
// 统计grid2中的子岛屿个数，边统计边淹没
int count=0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j]==1){
dfs(i,j,grid2);
count++;
}
}
}
return count;
}
};694. 不同岛屿的个数
在第200题的基础上，本题只需要在进行上下左右遍历时记录好次序即可
- 在递归函数dfs中增加一个字符串，用来记录遍历的过程；增加一个int的start标志位，用来记录方向
注意：在
void dfs(int i, int j, vector<vector<int>> &grid, string &sb, int start)中，sb要设为引用（即：string &sb），这样才能在void中修改后，sb也随着发生变化。若不是引用,则退出dfs函数后，sb仍为空，没有效果。比如：// appending to string #include <iostream> #include <string> #include <algorithm> using namespace std; void helper(string & a){ a+="!"; // return a; } void helper1(string a){ a+="+++"; } int main () { string a="hello"; helper(a); cout<<a<<endl; // hello! helper1(a); cout<<a<<endl; // 无效，仍为hello! }
//#include <bits/stdc++.h>
//using namespace std;
class Solution {
public:
// 函数功能：找到一小块陆地，并从这块陆地开始，淹没周围其他陆地
void dfs(int i, int j, vector<vector<int>> &grid, string &sb, int start) {
int m = grid.size();
int n = grid[0].size();
// 找到了陆地
if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
grid[i][j] = 0; // 找到当前陆地，并淹没
sb.append(to_string(start)).append(",");
// 以当前节点为中心，继续淹没周围陆地.分别用1234作为标记
dfs(i, j + 1, grid, sb, 1); // 上
dfs(i, j - 1, grid, sb, 2);// 下
dfs(i - 1, j, grid, sb, 3);// 左
dfs(i + 1, j, grid, sb, 4);// 右
}
}
int numDistinctIslands(vector<vector<int>> &grid) {
unordered_set<string> res;
int m = grid.size();
int n = grid[0].size();
// 遍历整个陆地
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 如果当前的这小块是陆地，则执行淹没操作，并把count+1
if (grid[i][j] == 1) {
string sb="";
dfs(i, j, grid, sb, 6); // 一开始进入，start相当于一个flag，随便一个（除了1234的）数字都可以
// cout<<sb<<endl;
res.emplace(sb);
}
}
}
return res.size();
}
};
//int main() {
// Solution so;
// vector<vector<int>> grid = {{1, 1, 0, 1, 1},
// {1, 0, 0, 0, 0},
// {0, 0, 0, 0, 1},
// {1, 1, 0, 1, 1}};
// cout << so.numDistinctIslands(grid)<<endl;
//}
