目录
建议backtrack/dfs/traverse 函数尽可能保持void
前言
本文的主要思路来源于bilibil博主labuladong，他的算法网页为：
越看东哥越觉得牛逼，强烈建议大家去东哥的网站上刷题，狠狠推荐！
二维矩阵的DFS框架代码
岛屿系列算法问题是经典的面试高频题，看起来可能比较无从下手，但是这类问题都可以使用dfs框架来完成，掌握了二维数组的dfs框架，这样的问题就会轻松很多，本文就来把这些问题一网打尽。
岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。
本文主要来讲解如何用 DFS 算法来秒杀岛屿系列题目：
那么如何在二维矩阵中使用 DFS 搜索呢？如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。
如果学习过二叉树递归遍历中的模板的话，完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架：
让我们简单回顾一下二叉树中的递归遍历模板：
// 二叉树遍历框架
void traverse(TreeNode* root) {
traverse(root->left);
traverse(root->right);
}下面就是我们的二维矩阵的dfs框架：
因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路，如果你能理解下面这段代码，那么搞定所有岛屿系列题目都很简单。
// 二维矩阵遍历框架
void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入当前节点 (i, j)
visited[i][j] = true;
// 进入相邻节点（四叉树）
// 上
dfs(grid, i - 1, j, visited);
// 下
dfs(grid, i + 1, j, visited);
// 左
dfs(grid, i, j - 1, visited);
// 右
dfs(grid, i, j + 1, visited);
}岛屿数量
题目思路：
题目链接：
题目会输入一个二维数组 grid，其中只包含 0 或者 1，0 代表海水，1 代表陆地，且假设该矩阵四周都是被海水包围着的。
我们说连成片的陆地形成岛屿，那么请你写一个算法，计算这个矩阵 grid 中岛屿的个数。
比如说题目给你输入下面这个 grid 有四片岛屿，算法应该返回 4：
思路很简单，关键在于如何寻找并标记「岛屿」，这就要 DFS 算法发挥作用了，我们直接看解法代码：
代码实现：
#include<bits/stdc++.h>
using namespace std;
//前向声明
void dfs(int i, int j, vector<vector<int>>& grid, int n, int m);
// 主函数，计算岛屿数量
int numIslands(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
int Island_num = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 1){
// 每发现一个岛屿，岛屿数量加一
Island_num++;
// 然后使用 DFS 将岛屿淹了
dfs(i, j, grid, n, m);
}
}
}
return Island_num;
}
//dfs的作用是利用深度优先算法将grid[i][j]这块陆地以及周围的陆地全部变成海洋，表示已经访问过
void dfs(int i, int j, vector<vector<int>>& grid, int n, int m){
//注意这里关于边界条件应该先判断，然后再判断是否为海洋，不然可能数组越界
if(i<0 || j<0 || i>=n || j>=m){
return;
}
if(grid[i][j] == 0){
return;
}
// 将 (i, j) 变成海水
grid[i][j] = 0;
// 淹没上下左右的陆地，这里下面四个函数调用顺序随意
dfs(i, j-1, grid, n, m);//左
dfs(i, j+1, grid, n, m);//右
dfs(i-1, j, grid, n, m);//上
dfs(i+1, j, grid, n, m);//下
}
int main(){
//grid是一个二维数组，表示的是陆地和海洋，1表示陆地，0表示海洋
vector<vector<int>> grid = {
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1}
};
cout << "numIslands: " << numIslands(grid);
return 0;
}为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。
因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。
这类可以凭借技巧不使用visited的 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~
洪水填充有点蔓延的感觉，简直是：
妙蛙种子吃着妙脆角妙进了米奇妙妙屋，妙到家了！！！
封闭岛屿数量
题目思路
题目链接：
1254. 统计封闭岛屿的数目 - 力扣（LeetCode）
题目描述：
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
比如题目给你输入如下这个二维矩阵：
算法返回 2，只有图中灰色部分的 0 是四周全都被海水包围着的「封闭岛屿」。
那么如何判断「封闭岛屿」呢？其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？
代码实现：
#include<bits/stdc++.h>
using namespace std;
void dfs(int i, int j, int n, int m, vector<vector<int>>& grid);
int Island_num(vector<vector<int>>& grid){
int n = grid.size();
int m = grid[0].size();
int island_num = 0;
//将第一列和最后一列的岛屿进行清除
for(int i=0; i<n; i++){
dfs(i, 0, n, m, grid);
dfs(i, m-1, n, m, grid);
}
//将第一行和最后一行的岛屿进行清除
for(int i=0; i<m; i++){
dfs(0, i, n, m, grid);
dfs(n-1, i, n, m, grid);
}
// 遍历 grid，剩下的岛屿都是封闭岛屿
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 1){
island_num++;
dfs(i, j, n, m, grid);
}
}
}
return island_num;
}
void dfs(int i, int j, int n, int m, vector<vector<int>>& grid){
//如果边界越界的话，就返回
if(i<0 || j<0 || i>=n || j>=m){
return;
}
//如果是海水的话，就直接返回
if(grid[i][j] == 0){
return;
}
//把陆地淹没成海水
grid[i][j] = 0;
dfs(i-1, j, n, m, grid);
dfs(i+1, j, n, m, grid);
dfs(i, j-1, n, m, grid);
dfs(i, j+1, n, m, grid);
}
int main(){
//1表示陆地，0表示海水
vector<vector<int>> grid = {
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 0, 1, 0, 0},
{0, 0, 0, 0, 1}
};
cout << "island_num: " << Island_num(grid);
return 0;
}子岛屿数量
题目思路：
题目链接：
题目描述：
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
grid1和grid2大小一模一样
请你返回 grid2 中 子岛屿 的 数目 。
这道题的关键在于，如何快速判断子岛屿？
什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么整个岛屿 B 就不是岛屿 A 的子岛。
那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
代码实现：
class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid2.size(), n = grid2[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid2[i][j] == 1 && grid1[i][j] == 0) {
// 这个岛屿肯定不是子岛，淹掉
dfs(grid2, i, j);
}
}
}
// 现在 grid2 中剩下的岛屿都是子岛，计算岛屿数量
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid2[i][j] == 1) {
res++;
dfs(grid2, i, j, m, n);
}
}
}
return res;
}
private:
// 从 (i, j) 开始，将与之相邻的陆地都变成海水
void dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
if (grid[i][j] == 0) {
return;
}
grid[i][j] = 0;
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
};这道题的思路和计算「封闭岛屿」数量的思路有些类似，只不过后者排除那些靠边的岛屿，前者排除那些grid2中的岛屿但是不可能是grid1子岛的岛屿。
这里排除grid2中的非grid1的子岛核心代码是：
if (grid2[i][j] == 1 && grid1[i][j] == 0) {
// 这个岛屿肯定不是子岛，淹掉
dfs(grid2, i, j);
}又是一个很巧妙的技巧！
妙蛙种子吃着妙脆角妙进了米奇妙妙屋，妙到家了！！！
岛屿的最大面积
题目思路：
题目链接：
题目描述：
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
比如题目给你输入如下一个二维矩阵：
其中面积最大的是橘红色的岛屿，算法返回它的面积 6。
这题的大体思路和之前完全一样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。
代码实现：
#include<bits/stdc++.h>
using namespace std;
//前向声明
void dfs(int& max_island_temp, int i, int j, vector<vector<int>>& grid, int n, int m);
// 主函数，计算面积最大岛屿
int Max_Island(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
int max_island = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 1){
// 每发现一个岛屿，就使用 DFS 将岛屿淹了
int max_island_temp = 0;
dfs(max_island_temp, i, j, grid, n, m);
max_island = max(max_island, max_island_temp);
}
}
}
return max_island;
}
//dfs的作用是利用深度优先算法将grid[i][j]这块陆地以及周围的陆地全部变成海洋，表示已经访问过
void dfs(int& max_island_temp, int i, int j, vector<vector<int>>& grid, int n, int m){
//注意这里关于边界条件应该先判断，然后再判断是否为海洋，不然可能数组越界
if(i<0 || j<0 || i>=n || j>=m){
return;
}
if(grid[i][j] == 0){
return;
}
// 将 (i, j) 变成海水
grid[i][j] = 0;
max_island_temp++;
// 淹没上下左右的陆地，这里下面四个函数调用顺序随意
dfs(max_island_temp, i, j-1, grid, n, m);//左
dfs(max_island_temp, i, j+1, grid, n, m);//右
dfs(max_island_temp, i-1, j, grid, n, m);//上
dfs(max_island_temp, i+1, j, grid, n, m);//下
}
int main(){
//grid是一个二维数组，表示的是陆地和海洋，1表示陆地，0表示海洋
vector<vector<int>> grid = {
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1}
};
cout << "max_Island: " << Max_Island(grid);
return 0;
}关于计算岛屿的面积的时候，识别到grid [ i ] [ j ]为陆地的时候就+1，只需要修改这样一点逻辑，就可以达到计算岛屿面积的需求。
// 将 (i, j) 变成海水
grid[i][j] = 0;
//记录当前岛屿面积+1
max_island_temp++;岛屿问题总结
岛屿问题如何去做呢？
我的回答就是：背模板
labuladong的模板化刷题思路真的是太厉害了，只要将核心的模板记忆下来，我们将会发现核心问题已经迎刃而解了，背诵模板的基础上你可以适当做点题，这里有两个作用：
1.加深对于模板的记忆，不用太过于想模板怎么来的，记住模板就行了。
现在我有点觉得刷算法题和做数学题是很相似的，算法题中的模板就像数学题中的公式，我问你你用数学中的公式的时候，你需要很细致了解公式推导过程吗？你肯定就会说我会做题就行了。
同样类似的，想出来这些模板的天才，他们的想法我们也不需要很细究，我们大致理解，能够感受框架流程，思想上理解这样做是对的，清晰记忆框架，在框架基础上来做题这才是我们所需要的，如果你非要死磕从0->1这个框架为什么这样写的话，emm，那可能有点较真了，虽然有时候我也会较真为什么这样做，不过后面想到最后，还是觉得应该背模板了。
前两天刷到一个视频，说的是计算机学生在面试的时候应该如何去做算法题，其实正解就是一秒出思路，迅速把代码框架敲出来，然后在面试官给定时间内大多数时间都是进行微调，比如哪里变量漏写了一个或者不小心写了个小bug。要想做到这一点的话，本质上要求的不是我们有多好的脑子，对算法有多么深刻的理解，本质上需要的就是背诵。
如果机考的时候现场苦思冥想题目，那只能说明我们刷题不够多，对这些还没有达到背诵的程度。如果真的有那种需要我们苦思冥想的题目，那大概率我们也不会写，当然公司大概率也不会出这些题。
所以我现在的理解就是：拥抱模板~
2.多了解一下模板的灵活变通题型，有些题型可能没有见过的话还是很难想到的，或者说我们很难想到最简便的那种方式。
比如在岛屿数量这个问题中，我们熟悉模板之后，需要再做一些别的题目，这些题目的核心虽然都是用的岛屿的模板，但是里面有一些细节上的操作和一些思路还是不太一样的，有意识地练习和积累这些模板的灵活运用和变通题型，是提高在压力环境下快速解决问题能力的关键。
建议backtrack/dfs/traverse 函数尽可能保持void
这里可能只是简单提一下这个结论，由于我现在刷题量还不是很多，没办法很详细地来进行对比，所以下面我将简单谈论一下。
递归算法主要有两种思维模式，一种是「遍历」的思维，一种是「分解问题」的思维。
遍历 (Traversal): 这种思维模式主要用于探索一个结构 (如树、图、或者通过状态变化形成的搜索空间) 中的所有可能路径或所有元素。递归在这里的作用是深入到结构的下一层或下一个可能的状态。它往往用于查找所有解、执行某种访问操作，或者判断某个属性是否存在于整个结构中。前面提到的 Backtracking 和 DFS (用于图或树遍历) 很多时候就属于这种思维模式的应用。
分解问题 (Problem Decomposition / Divide and Conquer): 这种思维模式是将一个大问题分解成一个或多个规模更小、但类型相同的子问题，然后递归地解决这些子问题，最后将子问题的解组合起来形成原问题的解。这种模式强调的是问题的结构本身可以被递归地拆分。
凭借我现有的经验来说，我觉得递归算法中遍历类题目要比分解类题目多，在这些遍历类问题中我们一般推荐就是尽量将backtrack/dfs/traverse 函数函数的返回值设置成void类型。
有些遍历函数加返回值是为了提前终止递归，目标是找到一个解并停止，在某些问题中，你只需要找到第一个满足条件的解就足够了。这里的话其实可以给backtrack/dfs/traverse添加返回值，从而达到快速退出递归函数的效果。
但有我认为是没有必要的，在backtrack/dfs/traverse中搅和进去一个返回值的话，个人认为代码不太好理解，因为这样递归函数中除了考虑basecase以及遍历和递归深入问题之外，还需要额外考虑一下函数返回值的处理问题，增加了我们问题处理的复杂程度。
OK这时候你就会想问了，那么如果目标是找到一个解并停止，那这样应该怎么做呢？
可以添加一个 found 外部变量，通过给backtrack/dfs/traverse传入额外的变量来进行控制。具体的题目对应有数独问题：
day22——回溯算法，全排列，生成二进制串，数独-CSDN博客
通过一个found变量来实现，如果找到一个有效解就快速退出递归。
emm，这里只是举了一个例子，其实我想说的是，为了更便于理解，在实际的递归问题中，当你想要给递归函数backtrack/dfs/traverse加上返回值的话，建议可以先想一下能不能通过其他手段来避免返回值的使用，比如说增加传入一个变量之类的，实在没办法或者用传入变量方式来解决问题很复杂，再来考虑选择增加返回值。