前言
DFS深度优先遍历，关于DFS类型的题目解题步骤是份固定的：
- 准备工作：确定向那几个方向进行扩展；
- 编写DFS函数，确定扩展条件；
- 确定DFS入口，依次进行深搜。
下面将借助一些经典面试题来具体分析。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单
DFS经典题目
200. 岛屿数量
思路：可以依次遍历每个位置，将岛屿看成一个整体，对每个岛屿统计一次。细节：在统计每个岛屿的每个位置时，将已经统计过的位置进行标记，防止多次统计。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={-1,1,0,0}; //向左右进行扩展
int dy[]={0,0,1,-1}; //上下进行扩展
function<void(int,int)> dfs=[&](int x,int y) //进行递归调用,向左右进行扩展
{
grid[x][y]='0'; //将同一个区域的1全部置为0
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]=='1') dfs(a,b);
}
};
int ret=0;
for(int i=0;i<n;i++) //依次遍历
{
for(int j=0;j<m;j++)
{
if(grid[i][j]=='1')
{
ret++;
dfs(i,j);
}
}
}
return ret;
}
};695. 岛屿的最大面积
此题是上一题的一个变形，此题不再是统计岛屿，而是统计岛屿的最大面积，在进入每一块岛屿的时候将每一块岛屿的面积直接进行返回，同时对已经统计的岛屿进行标记。
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
function<int(int,int)> dfs=[&](int x,int y)
{
int ret=1;
grid[x][y]=0;
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) ret+=dfs(a,b); //向周围统计岛屿的面积
}
return ret;
};
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==1)
ans=max(ans,dfs(i,j)); //找出最大岛屿
}
}
return ans;
}
};面试题 16.19. 水域大小
与第200题相似，不同点在于此题需要向对角线进行扩展。
class Solution {
public:
vector<int> pondSizes(vector<vector<int>>& land) {
int n=land.size(),m=land[0].size();
int dx[]={0,0,1,1,1,-1,-1,-1}; //统计向四周进行扩展的偏移量
int dy[]={1,-1,0,1,-1,0,1,-1};
function<int(int,int)> dfs=[&](int x,int y)
{
int ret=1;
land[x][y]=-1;
for(int k=0;k<8;k++) //向四周进行扩展
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&land[a][b]==0) ret+=dfs(a,b);
}
return ret;
};
vector<int> ans;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(land[i][j]==0)
ans.push_back(dfs(i,j));
}
sort(ans.begin(),ans.end());
return ans;
}
};LCS 03. 主题空间
此题多了一个限制，与走廊相邻的不能进行统计，所以在更新答案之前要进行依次判定，判断是否与走廊相邻。可以使用一个变量flag(flag必须被所有递归函数拿到)进行标记，如果与走廊相邻就左标记。
class Solution {
public:
int largestArea(vector<string>& grid) {
int n=grid.size(),m=grid[0].size();
int ans=0,flag=1;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
function<int(int,int,char)> dfs=[&](int x,int y,char p)
{
int ret=1;
grid[x][y]='9';
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a<0||a>n-1||b<0||b>m-1||grid[a][b]=='0') flag=0;
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==p) ret+=dfs(a,b,p);
}
return ret;
};
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
if(grid[i][j]!='0'&&grid[i][j]<='5')
{
flag=1;
int tmp=dfs(i,j,grid[i][j]);
if(flag) ans=max(ans,tmp);
}
}
}
return ans;
}
};463. 岛屿的周长
思路：此题关键在于如何统计边长；当旁边是河时，将周长+1，当旁边不是河时，向旁边扩。
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
function<int(int ,int)> dfs=[&](int x,int y)
{
int ret=0;
grid[x][y]=-1;
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a<0||a>=n||b<0||b>=m||grid[a][b]==0) ret++; //旁边是河,周长+1
else if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) ret+=dfs(a,b); //旁边不是河,向旁边扩
}
return ret;
};
int ret=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(grid[i][j]==1) ret=dfs(i,j);
}
return ret;
}
};2658. 网格图中鱼的最大数目
思路：与695题基本一样，还是找到最大的数目，将区域进行划分来统计最大的板块。
class Solution {
public:
int findMaxFish(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
function<int(int ,int)> dfs=[&](int x,int y)
{
int ret=grid[x][y];
grid[x][y]=-1;
for(int k=0;k<4;k++) //向左右进行扩展
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]>0) ret+=dfs(a,b);
}
return ret;
};
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(grid[i][j]>0) ans=max(ans,dfs(i,j));
}
return ans;
}
};1034. 边界着色
细节：此题需要特别注意将原本的数据与修改后的数据进行区分，否则在判断边界的时候会出现多判断的情况。
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int tar=grid[row][col];
vector<vector<int>> vis(n,vector<int>(m));
function<void(int,int)> dfs=[&](int x,int y)
{
vis[x][y]=1;
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==tar&&!vis[a][b]) dfs(a,b); //旁边存在相同的数,可以向左右扩展
else if(a<0||a>=n||b<0||b>=m||(grid[a][b]!=tar&&!vis[a][b])) grid[x][y]=color; //旁边存在不是tar的数据并且该数不是改变过的数
}
};
dfs(row,col);
return grid;
}
};1020. 飞地的数量
思路：向将与周边相邻的陆地单元格进行标记；在统计没有被标记的陆地单元格。
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
function<void(int,int)> dfs=[&](int x,int y)
{
grid[x][y]=-1; //对与边界相邻的单元格进行标记
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) dfs(a,b);
}
};
for(int i=0;i<n;i++) //遍历上下边界
{
if(grid[i][0]>0) dfs(i,0);
if(grid[i][m-1]>0) dfs(i,m-1);
}
for(int j=0;j<m;j++) //遍历左右边界
{
if(grid[0][j]>0) dfs(0,j);
if(grid[n-1][j]>0) dfs(n-1,j);
}
int ret=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(grid[i][j]>0) ret++;
return ret;
}
};2684. 矩阵中移动的最大次数
使用DFS向左边依次扩展，如果右边存在严格大于当前位置的数字，继续向右边扩展。
注意：此题如果直接使用DFS会导致超时，所以需要对代码进行优化；枚举第一列的每一个数据，在向后扩展的时候必定会出现重复计算的路径，所以在每一个位置计算完成后将结果记录下来，供后面的数使用。
class Solution {
public:
int maxMoves(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,-1,1};
vector<vector<int>> vist(n,vector<int>(m,-1)); //记录每一个位置的结果
function<int(int,int)> dfs=[&](int x,int y)
{
if(vist[x][y]!=-1) return vist[x][y]; //如果前面已经记录过就直接返回
int ret=0;
for(int k=0;k<3;k++)
{
int a=x+dx[k],b=y+1;
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]>grid[x][y])
ret=max(ret,dfs(a,b)+1);
}
vist[x][y]=ret; //将记录的结果存储起来
return ret;
};
int ans=0;
for(int i=0;i<n;i++)
ans=max(ans,dfs(i,0));
return ans;
}
};手撕DFS面试题
1254. 统计封闭岛屿的数目
此题与LCS 03题类似，在更新答案之前都需要判断合不合理；依旧是使用一个所有递归都能看到的变量来存储该区域时候满足条件。
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int ans=0,flag=0; //flag来存储区域是否满足条件
function<void(int,int)> dfs=[&](int x,int y)
{
grid[x][y]=-1;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==0) dfs(a,b);
else if(a<0||a>=n||b<0||b>=m) flag=0; //区域不满足条件
}
};
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
if(grid[i][j]==0)
{
flag=1;
dfs(i,j);
if(flag) ans++;
}
}
}
return ans;
}
};130. 被围绕的区域
思路：直接找中间部分，将中间部分修改为X较为复杂，此题可以使用正难则反，找出所有没有被包围的O，将这些O进行标记，其余没有没标记的O就是被围拦的部分了。
class Solution {
public:
void solve(vector<vector<char>>& nums) {
//正难则反
//直接将围绕区域的X变成O还需要判断,那不如直接将没有没围绕的进行标记,其余的没有被标记的不就是被围绕的嘛
int n=nums.size(),m=nums[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
function<void(int,int)> dfs=[&](int x,int y)
{
nums[x][y]='I';
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&nums[a][b]=='O') dfs(a,b);
}
};
for(int i=0;i<n;i++) //标记没有被包围的O
{
if(nums[i][0]=='O') dfs(i,0);
if(nums[i][m-1]=='O') dfs(i,m-1);
}
for(int i=0;i<m;i++)
{
if(nums[0][i]=='O') dfs(0,i);
if(nums[n-1][i]=='O') dfs(n-1,i);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(nums[i][j]=='O') nums[i][j]='X';
else if(nums[i][j]=='I') nums[i][j]='O';
}
}
}
};1905. 统计子岛屿
将两个矩阵进行比较，对grid2进行DFS，找出grid2中的每一个岛屿判断这些岛屿grid1中是否有即可。
class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int n=grid1.size(),m=grid1[0].size();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ans=0,flag=1;
function<void(int,int)> dfs=[&](int x,int y)
{
grid2[x][y]=-1; //对已经遍过的位置进行标记
if(grid1[x][y]!=1) flag=0; //grid1中没有该区域,该区域不是子岛屿
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid2[a][b]==1) dfs(a,b);
}
};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid2[i][j]>0)
{
flag=1;
dfs(i,j);
if(flag) ans++;
}
}
}
return ans;
}
};1391. 检查网格中是否存在有效路径
根据题目就是一个简单的判断是否存在有效路径问题，从(0,0)能不能到(n-1,m-1)，每个板块的路径都是固定的，只要确定板块和方向就能找到下一个位置。
如何将信息进行整合，如何判断下一步的位置：此题确实是递归，但是递归的实现并不难，难点在于如何确定来源以及如何确定下一步的位置。
先对信息进行整合，板块+方向----->下一个左边的位置。那是否可以使用一个矩阵描述不同板块在不同方向下的作用结果即下一个位置是在上下左右那个位置。
通过以上这个图就可以将板块与来源方向结合起来，进而确定下一个位置的坐标，其中-1表示没有下一个位置。0表示在上，1表示下，2表示左，3表示右。
class Solution {
public:
bool hasValidPath(vector<vector<int>>& grid) {
//使用一个数组来记录每个图片的来源对应的出处
int pipe[][4]={
{},
{-1,-1,3,2},
{1,0,-1,-1},
{-1,2,1,-1},
{-1,3,-1,1},
{2,-1,0,-1},
{3,-1,0,-1}
};
int dx[]={-1,1,0,0}; //将上下左右对应的x和y的增长情况存储起来
int dy[]={0,0,-1,1};
int n=grid.size(),m=grid[0].size();
vector<vector<int>> vist(n,vector<int>(m,-1));
function<bool(int,int,int)> dfs=[&](int x,int y,int dir)
{
if(vist[x][y]==1) return false;
vist[x][y]=1;
int next=pipe[grid[x][y]][dir],now=0; //从那个方向到下一个位置
if(next==-1) return false;
if(next==0) now=1; //now存储该位置在下一个位置的哪个方向,即与next相反,确定下一个位置的来源
else if(next==1) now=0;
else if(next==2) now=3;
else now=2;
if(x==n-1&&y==m-1) return true;
int a=x+dx[next],b=y+dy[next]; //下一个位置的坐标
if(a<0||a>=n||b<0||b>=m) return false;
return dfs(a,b,now);
};
for(int i=0;i<4;i++)
{
vist=vector<vector<int>>(n,vector<int>(m,-1)); //记忆化存储,让已经走过的地方不再走,防止死循环
if(dfs(0,0,i)) return true; //第一个位置向线下左右四个方向都试一遍
}
return false;
}
};417. 太平洋大西洋水流问题
分开处理,依次统计能够流向太平洋和大西洋的位置,在求其交集；
水从高出往低处流,最终一定留到大洋中,那就可以中大洋中出发,向高出走,只要是走到的位置一定都是可以留到大洋中的位置。
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& nums) {
//分开处理,依次统计能够流向太平洋和大西洋的位置,在求其交集
//水从高出往低处流,最终一定留到大洋中,那就可以中大洋中出发,向高出走,只要是走到的位置一定都是可以留到大洋中的位置
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n=nums.size(),m=nums[0].size();
vector<vector<int>> vistpa(n,vector<int>(m));
vector<vector<int>> vistat(n,vector<int>(m));
set<pair<int,int>> stpa;
set<pair<int,int>> stat;
//进行递归,(x,y)是左边,st存储可以流入大洋的水流,vist存储已经到达过的位置
function<void(int,int,set<pair<int,int>>&,vector<vector<int>>&)> dfs=[&](int x,int y,set<pair<int,int>>& st,vector<vector<int>>& vist)
{
if(vist[x][y]) return ;
vist[x][y]=1;
st.insert({x,y}); //将该位置存储起来
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&nums[a][b]>=nums[x][y]) dfs(a,b,st,vist);
}
};
//分别从上下左右找
for(int i=0;i<m;i++)
{
dfs(0,i,stpa,vistpa);
dfs(n-1,i,stat,vistat);
}
for(int i=0;i<n;i++)
{
dfs(i,0,stpa,vistpa);
dfs(i,m-1,stat,vistat);
}
//找交集
vector<vector<int>> ret;
for(auto& pa:stpa){
if(stat.count(pa)) ret.push_back({pa.first,pa.second});
}
return ret;
}
};529. 扫雷游戏
经典的扫雷游戏，相信大家都玩过。此题关键在于如何让空位置能够向外扩展，此时就可以采用DFS解决。
- 雷，直接返回；
- 是数字将board进行修改后返回；
- 是空位置，向8个方向扩展。
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int dx[]={-1,1,1,1,-1,-1,0,0};
int dy[]={0,0,1,-1,1,-1,-1,1};
int n=board.size(),m=board[0].size(),count;
function<int(int,int)> mine_count=[&](int x,int y) //计算周围雷的个数
{
int ret=0;
for(int k=0;k<8;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&board[a][b]=='M') ret++;
}
return ret;
};
function<void(int,int)> dfs=[&](int x,int y)
{
int count=mine_count(x,y);
if(count) board[x][y]='0'+count; //周围有雷
else //作为没有雷
{
board[x][y]='B';
for(int k=0;k<8;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&board[a][b]=='E') dfs(a,b);
}
}
};
if(board[click[0]][click[1]]=='M') board[click[0]][click[1]]='X'; //是雷
else dfs(click[0],click[1]); //不是雷
return board;
}
};1559. 二维网格图中探测环
如果要形成一个周长为4的矩形，只要有一个节点向上下左右任意一个方向能找到一个与其本身相同且已经到达过的位置，并且找到的位置不是当前位置的上一层栈帧(即不是当前位置的上一个位置)即可。
class Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n=grid.size(),m=grid[0].size();
vector<vector<int>> vist(n,vector<int>(m));
function<bool(int,int,int,int)> dfs=[&](int x,int y,int prev_x,int prev_y) //prev用来记录上一个位置
{
vist[x][y]=1;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a==prev_x&&b==prev_y) continue; //如果是上一个位置继续找
if(a>=0&&a<n&&b>=0&&b<m&&vist[a][b]&&grid[a][b]==grid[x][y]) return true; //找到满足条件的节点了
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==grid[x][y]) if(dfs(a,b,x,y)) return true;
}
return false;
};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(vist[i][j]) continue;
if(dfs(i,j,-1,-1)) return true;
}
}
return false;
}
};827. 最大人工岛
根据题目：可以将一个0填充为1。
那不妨枚举每一个0将两个没有连接的岛屿进行连接 。
具体实现：对矩阵中的每个岛屿进行编号，将每个岛屿的面积记录下来；枚举每一个0位置，将两个不相交的岛屿进行连接，此处需要注意每个岛屿只能计算依次。
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n=grid.size(),m=grid[0].size(),zero=0;
//先统计每个孤立岛屿的面积
vector<int> area(2); //统计每个岛屿的面积,空出两个位置使得下标一一对用
function<int(int,int)> dfs=[&](int x,int y)
{
grid[x][y]=area.size(); //对岛屿进行编号
int ret=1;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) ret+=dfs(a,b);
}
return ret;
};
for(int i=0;i<n;i++) //统计每个岛屿的面积
for(int j=0;j<m;j++)
if(grid[i][j]==1)
area.push_back(dfs(i,j));
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]) continue;
int sum=1;
unordered_set<int> have; //记录已经统计过的岛屿
for(int k=0;k<4;k++)
{
int a=i+dx[k],b=j+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]&&!have.count(grid[a][b]))
{
int index=grid[a][b];
have.insert(index);
sum+=area[grid[a][b]];
}
}
ans=max(ans,sum);
}
}
return ans==0?n*m:ans;
}
};总结
在前言部分对于DFS的解题思路已经进行了基本的介绍，基本上对于所有DFS都可以使用上面的方法，DFS最重要的就是确定在什么时候向四周进行扩展；对于一些难题可能需要对题目进行一定的划分，将题目抽象出来或使用一些解题技巧等。