一把王者的时间拿捏岛屿问题（dfs) c++

一.岛屿的数量

目录
一.岛屿的数量
二.岛屿的周长
三. 岛屿的最大面积
四统计封闭岛屿的数量
五.飞地的数量
六统计子岛屿的数量

对应letecode链接：
200. 岛屿数量 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

文章图片

解题思路：

我们首先明确一下岛屿问题中的网格结构是如何定义的，以方便我们后面的讨论。
网格问题是由 m ×n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿

文章图片

我们只需要两个for循环遍历数组遇到1就开始感染递归他的四个方向如果遇到1就将其改为0，如果不是1直接返回如果开越界也返回即可.

对应代码：

class Solution { public: int numIslands(vector>& grid) { int ans=0; for(int i=0; i>&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>visit; int numIslands(vector>& grid) { visit.resize(grid.size(),vector(grid[0].size())); int ans=0; for(int i=0; i>&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>& grid) { int m=grid.size(); int ans=0; int n=grid[0].size(); for(int i=0; i>&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即可下次进来就不会重复计算 returninfect(grid,row+1,col)+//四个方向的结果累加 infect(grid,row-1,col)+ infect(grid,row,col-1)+ infect(grid,row,col+1); } }};

同样的如果不想修改数组，我们可以定义一个二维数组记录访问过的位置：

class Solution { public: vector>visit; //记录二维表中某个位置是否被访问 int islandPerimeter(vector>& grid) { int m=grid.size(); int ans=0; int n=grid[0].size(); visit.resize(m,vector(n)); for(int i=0; i>&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; returninfect(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>visit; int maxAreaOfIsland(vector>& grid) { int ans=0; visit.resize(grid.size(),vector(grid[0].size())); for(int i=0; i>&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>& grid) { int ans=0; for(int i=0; i>&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>visit; //记录每个位置是否记录过 int closedIsland(vector>& grid) { visit.resize(grid.size(),vector(grid[0].size())); int ans=0; for(int i=0; i>&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>visit; int numEnclaves(vector>& grid) { visit.resize(grid.size(),vector(grid[0].size())); int m=grid.size(); int n=grid[0].size(); visit.resize(m,vector(n)); //记录每个位置是否被访问过 int ret=0; for(int i=0; i>&grid,int row,int col){if(row>=0&&row=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)

题目描述：

文章图片

解题思路：

【一把王者的时间拿捏岛屿问题（dfs)】这道题稍微复杂了一点，增加了一个判断条件，其实就是要求对grid2的一次dfs中所有遍历到的为1的地方在grid1中同样为1。可以将这道题看做是岛屿数量的类似题目。

对应代码：

同样的给出两种版本：

class Solution { public: vector>visit; int countSubIslands(vector>& grid1, vector>& grid2) { int m = grid2.size(), n = grid2[0].size(), res = 0; visit.resize(m,vector(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>& grid1, vector>& 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>& grid1, vector>& 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>& grid1, vector>& 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]; } };