BFS/DFS常用场景区分：

DFS常以递归形式实现，因为每次都要将一条路搜索到底后再回溯，所以适合求解所有路径的情况。

BFS常借助队列实现，每次将一层一层的向外扩展，所以常用于求解最短路径、求解路径长度和层次遍历中。

1.1091. 二进制矩阵中的最短路径

题目描述：

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格都的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

示例：

示例 1：
输入：grid = [[0,1],[1,0]]
输出：2

示例 2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

示例 3：
输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

解答描述：

首先，该题要寻找从左上角到右下角的最短路径长度，所以考虑使用BFS，其次，要返回的是长度值，所以考虑在BFS过程中，分层进行，每经过一层就记录下来层数，最终到达右下角的层数就是最短路径长度。

另外只需要注意一点，该题的方向是八个方向，上下左右、左上、左下、右上、右下。

代码：

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        //BFS最短路径 
        int n=grid.size();
        int dx[8]={0,0,1,-1,1,-1,1,-1};
        int dy[8]={1,-1,0,0,1,-1,-1,1};
        if(grid[0][0]!=0 || grid[n-1][n-1]!=0)
        {
            return -1;
        }
        if(n==1)
        {
            return 1;
        }
     
        queue<pair<int,int>> q;
        q.emplace(0,0);
        grid[0][0]=1;   
        int path=1;

        while(!q.empty())
        {
            int len=q.size();//相当于层次遍历，每经过一层 path+1
            path++; 
            while(len--)
            {
                int x=q.front().first;
                int y=q.front().second;
                q.pop();
 
                for(int i=0;i<8;i++)
                {
                    int new_x=x+dx[i];
                    int new_y=y+dy[i];
                    if(new_x<n && new_x>=0 && new_y<n && new_y>=0 && grid[new_x][new_y]==0)
                    {
                        q.emplace(new_x,new_y);
                        grid[new_x][new_y]=1;
                        if(new_x==n-1 &&new_y==n-1)
                        {
                            return path;
                        }
                    }
                }
            }
              
        }
        return -1;
    }
};

2.130. 被围绕的区域

题目描述：

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例：

解答描述：

该题最关键的一点是，直接从内部找所有被包围的O是很难的，但是边界上的O或者与边界直接或间接相邻的O都被认为是不被包围，这是好找的。

因为，需要找到所有的能被到达的点，所以考虑DFS。

首先，分别找到四个边界上的所有O，然后从这些点各个方向递归的DFS查找所有可以到达的O，并标记下来，不需要使用标记数组，直接修改board为特殊标记即可。

然后遍历整个二维矩阵，对现标记仍为O的，表示这个会被围住的O，直接修改为X即可，对现标记为特殊标记#的，表示这个边界可达的O，不会被围住，需要修改回原来的O.

代码：

class Solution {
public:
    void DFS(vector<vector<char>> &board,int s,int t,int rows,int cols)
    {
        if(s>=0 && s<rows && t>=0 && t<cols && board[s][t]=='O')
        {
            board[s][t]='#';//标记被访问过
            DFS(board,s+1,t,rows,cols);
            DFS(board,s-1,t,rows,cols);
            DFS(board,s,t+1,rows,cols);
            DFS(board,s,t-1,rows,cols);
        }
        else
        {
            return ;
        }

    }
    void solve(vector<vector<char>>& board) {
        int rows=board.size();
        if(rows==0)
        {
            return ;
        }
        int cols=board[0].size();
        //先找到边界上的点，以边界上的0点作为起点 进行DFS，并将所有搜索到的0记录
        for(int i=0;i<rows;i++)
        {
            DFS(board,i,0,rows,cols);//左边界
            DFS(board,i,cols-1,rows,cols);//右边界
        }
        for(int i=1;i<cols-1;i++)
        {
            DFS(board,0,i,rows,cols);//上边界
            DFS(board,rows-1,i,rows,cols);//下边界
        }
        //然后遍历整个矩阵，如果被标记过的0，说明不是被围住的，那么就不需要改变
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(board[i][j]=='O')
                {
                    board[i][j]='X';
                }
                else if(board[i][j]=='#')
                {
                    board[i][j]='O';
                }
            }
        }
    }
};

3.797. 所有可能的路径

题目描述：

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例：

解答描述：

该题要找出所有从节点 0 到节点 n-1 的路径，很显然直接从节点0到节点n-1DFS即可。

从节点0开始，递归遍历当前节点的所有邻接点，当当前节点等于n-1时，递归结束，否则，将当前节点出栈，继续递归。

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    //DFS递归查询从s到t的路线
    void DFS(vector<vector<int>>& graph,int s,int t)
    {
        if(s==t)
        {
            ans.push_back(temp);
            return ;
        }
        for(int i=0;i<graph[s].size();i++)
        {
            int y=graph[s][i];
            temp.push_back(y);
            DFS(graph,y,t);
            temp.pop_back();
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n=graph.size();
        temp.push_back(0);
        DFS(graph,0,n-1);
        return ans;
    }
};

最后

以上就是老实灯泡为你收集整理的算法基础/BFS/DFS1.1091. 二进制矩阵中的最短路径2.130. 被围绕的区域3.797. 所有可能的路径的全部内容，希望文章能够帮你解决算法基础/BFS/DFS1.1091. 二进制矩阵中的最短路径2.130. 被围绕的区域3.797. 所有可能的路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。