最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

[算法笔记] DFS搜索

来源：博客园

\(\text {DFS}\) 深度优先搜索

深度优先搜索，简称\(\text {DFS}\)（\(\text {Depth First Search}\)），顾名思义，就是搜索时的深度优先。


(相关资料图)

\(\text {DFS}\) 的本质其实是暴力枚举，只不过 \(\text {DFS}\) 在枚举时会检测当前枚举的选项是否符合条件，

如果符合，保存此选项，枚举下一个选项；反之更换一个选项，尝试此选项是否合法；但如果此时

发现没有可枚举的选项了，也就是所有的选项有不合法，进行「回溯」操作，更换上一个选项。

这样，枚举时就可以避免枚举许多无效的状态，以此节省时间。

可以举一个这样的例子：\(\text {DFS}\) 是一个有点智慧的人，他会想想自己干的事情有没有意义，

没有的话就放弃这个事情；

而枚举就是一个老实的人，他会老老实实的把所有活都干完，但却不知道自己干了一堆

没有意义的事。

刚刚所说 \(\text {DFS}\) 其实是图论中的一个概念。在搜索中常常指回溯算法，它们之间的关系在此不多说明，

只需知道 \(\text {DFS}\) 是一种搜索的算法即可。

\(\text {DFS}\) 的常见形式如下

void dfs(当前枚举到的选项){    if(所有的状态都枚举完毕){        输出/保存结果        return;    }    for(枚举当前选项)        if(这个选项是合法的){            记录这个选项            dfs(下一层枚举的状态);            取消这个选项        }}

给定一个 \(N \times M\) 方格的迷宫，迷宫里有 \(T\) 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标 \(SX,SY\) 和终点坐标 \(FX,FY\)，每个障碍物的 \(X,Y\)，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

\(N \le M \le 5\)

这题我们可以枚举移动的方向，记录，再判断路上有没有障碍物，很明显时间允许，可以 \(\color {green} {\texttt {AC}}\)，但要是 \(N \le M \le 30\) 呢？

这时，我们就可以使用 \(\text {DFS}\) 了。

我们枚举上下左右四个方向，同时判断移动的方向有没有障碍物和有没有走过，分别用 \(a\) 和 \(note\) 记录，

再用一个 \(sum\) 记录解的数量，用 \(x,y\) 记录当前 \(dfs\) 枚举到的位置，代码：

#includeusing namespace std;int n,m,t,fx,fy,sx,sy,sum;int a[6][6],note[6][6],next1[5][2] = {{114514,1919810},{0,1},{1,0},{0,-1},{-1,0}}; // 存储地图和走过的位置void dfs(int x,int y){    if(x == fx && y == fy){ // 如果到了终点        sum ++; // 记录解的数量        return;    }    for(int i = 1;i <= 4;i ++){ // 枚举方向        int next_x = x + next1[i][0],next_y = y + next1[i][1]; // 计算下一步的坐标        if(!a[next_x][next_y] && !note[next_x][next_y]){ // 如果没有障碍物且也没走过            note[next_x][next_y] = 1; // 标记为走过            dfs(next_x,next_y); // 继续走迷宫            note[next_x][next_y] = 0; // 走完后恢复，方便下一次枚举        }    }}int main(){    cin>>n>>m>>t;    cin>>sx>>sy>>fx>>fy;    for(int i = 1;i <= t;i ++){        int x,y;        cin>>x>>y;        a[x][y] = 1;    } // 以上为输入    a[sx][sy] = 1; // 标记起点为障碍物，防止无限来回    for(int i = 0;i <= n + 1;i ++)        for(int j = 0;j <= m + 1;j ++)            if(i == 0 || i == n + 1 || j == 0 || j == m + 1)a[i][j] = 1; // 标记边缘为障碍物    dfs(sx,sy); // go,go,go！开始走迷宫    cout<

完美 \(\color {green} {\texttt {AC}}\)！\(\text {DFS}\) 太厉害了吧！但还记得我说的吗？\(\text {DFS}\) 只是个有点智慧的人，如果有一个迷宫，但是它有许多岔路口，而且它有一个超级长的死胡同，会怎样？很明显，\(\text{DFS}\) 越走越深，最后在大量的回溯枚举中 \(\texttt {TLE}\)……也就是说，\(\text {DFS}\) 是「不撞南墙不回头」，不遇到非合法情况他就会一直走下去，有的时候真的会有问题……这时，\(\text {BFS}\) 就该出场了。欲知后事如何，且看下回分解。

关键词：