一.岛屿的数量
二.岛屿的周长
三. 岛屿的最大面积
四 统计封闭岛屿的数量
五. 飞地的数量
六 统计子岛屿的数量
对应letecode链接:
200. 岛屿数量 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
我们首先明确一下岛屿问题中的网格结构是如何定义的,以方便我们后面的讨论。
网格问题是由 m ×n 个小方格组成一个网格,每个小方格与其上下左右四个方格认为是相邻的,要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子,数字为 1 的格子看成陆地格子,这样相邻的陆地格子就连接成一个岛屿
我们只需要两个for循环遍历数组遇到1就开始感染递归他的四个方向如果遇到1就将其改为0,如果不是1直接返回如果开越界也返回即可.
对应代码:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int ans=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1'){//如果是1就递归去感染
ans++;//数量加加
infect(grid,i,j);
}
}
}
return ans;
}
void infect(vector<vector<char>>&board,int i,int j){
if(i<0||i==board.size()||j<0||j==board[0].size()||board[i][j]!='1'){
//越界直接返回或者不是字符一
return;
}
board[i][j]='0';//将其该为0
//向四个方向感染
infect(board,i-1,j);
infect(board,i+1,j);
infect(board,i,j-1);
infect(board,i,j+1);
}
};
不过了这样修该了原来的数组,博主感觉不太好感觉太挫了,博主给出另外一种解法:定义一个二维数组记录访问过的位置即可。下面给出代码:
class Solution {
public:
vector<vector<bool>>visit;
int numIslands(vector<vector<char>>& grid) {
visit.resize(grid.size(),vector<bool>(grid[0].size()));
int ans=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1'&&!visit[i][j]){//已经访问过了不要再访问了
ans++;
infect(grid,i,j);
}
}
}
return ans;
}
void infect(vector<vector<char>>&board,int i,int j){
if(i<0||i==board.size()||j<0||j==board[0].size()){//越界直接返回
return;
}
if(board[i][j]=='0'){
return;//不是字符1也直接返回
}
if(visit[i][j]){//已经访问过了直接返回
return;
}
visit[i][j]=true;//记录
//往四个方向感染
infect(board,i-1,j);
infect(board,i+1,j);
infect(board,i,j-1);
infect(board,i,j+1);
}
};
463. 岛屿的周长 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
本题思路和上题基本差不多,只不过本题如果到达边界我们需要返回1,这是因为如果越界了说明找到了周长之中的一条边。同样的我们需要将递归途中遇到的1全部改为其他数字否则递归将无法停止
在这里我们选择将其改为2.:
对应代码:
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int m=grid.size();
int ans=0;
int n=grid[0].size();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){//如果为1直接记录感染记录答案
ans+=infect(grid,i,j);
}
}
}
return ans;
}
int infect(vector<vector<int>>&grid,int row ,int col){
if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
return 1;
}
else if(grid[row][col]==2){//说明之前已经访问过了
return 0;
}
else if(grid[row][col]==0){//等于0返回
return 1;
}
else{
grid[row][col]=2;//说明是1将其改成2即可下次进来就不会重复计算
return infect(grid,row+1,col)+//四个方向的结果累加
infect(grid,row-1,col)+
infect(grid,row,col-1)+
infect(grid,row,col+1);
}
}
};
同样的如果不想修改数组,我们可以定义一个二维数组记录访问过的位置:
class Solution {
public:
vector<vector<bool>>visit;//记录二维表中某个位置是否被访问
int islandPerimeter(vector<vector<int>>& grid) {
int m=grid.size();
int ans=0;
int n=grid[0].size();
visit.resize(m,vector<bool>(n));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1&&!visit[i][j]){//如果已经被访问过了直接跳过
ans+=infect(grid,i,j);
}
}
}
return ans;
}
int infect(vector<vector<int>>&grid,int row ,int col){
if(row>=grid.size()||col>=grid[0].size()||row<0||col<0){//越界返回1说明是边界
return 1;
}
else if(visit[row][col]){//说明之前已经访问过了
return 0;
}
else if(grid[row][col]==0){//等于0返回
return 1;
}
else{
visit[row][col]=true;
return infect(grid,row+1,col)+//四个方向的结果累加
infect(grid,row-1,col)+
infect(grid,row,col-1)+
infect(grid,row,col+1);
}
}
};
剑指 Offer II 105. 岛屿的最大面积 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
本题思路和上题基本一模一样,上题是ans+=这个题只需要和返回值做比较即可。
对应代码:
class Solution {
public:
vector<vector<bool>>visit;
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans=0;
visit.resize(grid.size(),vector<bool>(grid[0].size()));
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]==1){//如果等于1就感染更新答案
ans=max(dfs(grid,i,j),ans);
}
}
}
return ans;
}
int dfs(vector<vector<int>>&grid,int row,int col){
if(row<0||col<0||row>=grid.size()||col>=grid[0].size()||visit[row][col]){
return 0;//visit[row][col]=true说明已经访问过了
}
else if(grid[row][col]==1){
visit[row][col]=true;
return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//自己加上四个方向的数量
+dfs(grid,row+1,col)+dfs(grid,row-1,col);
}
//说明它等于grid[row][col]=0直接返回0即可
return 0;
}
};
同样的给出两种方式一种使用一个二维数组记录位置,第二种方式是改变原数组中的值。
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]==1){//等于1向四个方向感染并更新答案
ans=max(dfs(grid,i,j),ans);
}
}
}
return ans;
}
int dfs(vector<vector<int>>&grid,int row,int col){
if(row<0||col<0||row>=grid.size()||col>=grid[0].size()){
return 0;
}
else if(grid[row][col]==1){
grid[row][col]=0;//访问过将其改为0;
return 1+dfs(grid,row,col-1)+dfs(grid,row,col+1)//四个方向递归
+dfs(grid,row+1,col)+dfs(grid,row-1,col);
}
//说明它等于grid[row][col]=0
return 0;
}
};
对应letecode链接:
1254. 统计封闭岛屿的数目 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
本题和上题思路不能说是相似真的是一模一样。思路都是如果一个位置为1向四个方向递归。
对应代码:
class Solution {
public:
vector<vector<bool>>visit;//记录每个位置是否记录过
int closedIsland(vector<vector<int>>& grid) {
visit.resize(grid.size(),vector<bool>(grid[0].size()));
int ans=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]==0&&!visit[i][j]){
if(!dfs(grid,i,j)){//如果返回的结果为false说明找到了
ans++;
}
}
}
}
return ans;
}
bool dfs(vector<vector<int>>&grid,int row,int col){
if(row<0||row>=grid.size()||col<0||col>=grid[0].size()){
return true;
}
if(grid[row][col]==1){
return false;
}
if(visit[row][col]){//判断是否已经访问过了
return false;
}
visit[row][col]=true;
//四个方向都要遍历不能只遍历一个方向
bool ret1= dfs(grid,row,col-1);//四个方向一点要遍历完毕才能停止
bool ret2=dfs(grid,row,col+1);
bool ret3=dfs(grid,row+1,col);
bool ret4=dfs(grid,row-1,col);
return ret1||ret2||ret3||ret4;//四个方向只要一个为true就直接返回
}
};
1020. 飞地的数量 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
本题等价于找到不和边缘相连的独立块的面积和,套用上题的模板即可。具体请看代码
对应代码:
class Solution {
public:
vector<vector<bool>>visit;
int numEnclaves(vector<vector<int>>& grid) {
visit.resize(grid.size(),vector<bool>(grid[0].size()));
int m=grid.size();
int n=grid[0].size();
visit.resize(m,vector<bool>(n));//记录每个位置是否被访问过
int ret=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
//从边界开始感染
if(!i||!j||i==m-1||j==n-1&&grid[i][j]&&!visit[i][j]){//如果是边界向四方感
dfs(grid,i,j);
}
}
}
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]==1&&!visit[i][j]){//如果它是1并且没有被感染过
ret++;
}
}
}
return ret;
}
void dfs(vector<vector<int>>&grid,int row,int col){
if(row>=0&&row<grid.size()&&col<grid[0].size()&&col>=0&&!visit[row][col]&&grid[row][col]!=0){
visit[row][col]=true;
dfs(grid,row,col-1);
dfs(grid,row,col+1);
dfs(grid,row+1,col);
dfs(grid,row-1,col);
}
}
};
1905. 统计子岛屿 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
这道题稍微复杂了一点,增加了一个判断条件,其实就是要求对grid2的一次dfs中所有遍历到的为1的地方在grid1中同样为1。可以将这道题看做是 岛屿数量的类似题目。
对应代码:
同样的给出两种版本:
class Solution {
public:
vector<vector<bool>>visit;
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid2.size(), n = grid2[0].size(), res = 0;
visit.resize(m,vector<bool>(n));
for (int row = 0; row < m; row++)
for (int col = 0; col < n; col++)
if (grid2[row][col]&&!visit[row][col])//该点为1并且已经访问过了
res += dfs(grid1, grid2, row, col);
return res;
}
private:
bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() ||
!grid2[row][col]) return true;
if(visit[row][col])//访问过了之后直接返回
{
return true;
}
visit[row][col]=true;//将其标记为true说明已经访问过了
return
grid1[row][col]&dfs(grid1, grid2, row + 1, col) & dfs(grid1, grid2, row - 1, col) &dfs(grid1, grid2, row, col + 1) & dfs(grid1, grid2, row , col - 1) ;
}
};
方法二:修改原数组中的值:
class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid2.size(), n = grid2[0].size(), res = 0;
for (int row = 0; row < m; row++)
for (int col = 0; col < n; col++)
if (grid2[row][col])//如果是1
res += dfs(grid1, grid2, row, col);
return res;
}
private:
bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int row, int col) {
if(row < 0 || col < 0 || row >= grid2.size() || col >= grid2[0].size() ||
!grid2[row][col]) return true;
grid2[row][col] = 0; // 设置已经遍历过标志
//四个方向都遍历
return dfs(grid1, grid2, row + 1, col) & dfs(grid1, grid2, row - 1, col) &
dfs(grid1, grid2, row, col + 1) & dfs(grid1, grid2, row , col - 1) &
grid1[row][col];
}
};
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_56999918/article/details/123674375
内容来源于网络,如有侵权,请联系作者删除!