资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

【深度优先搜索篇】带你暴力dfs去破解飞机降落和八皇后问题(轻松拿捏版)

创作时间:

作者:

@小白创作中心

【深度优先搜索篇】带你暴力dfs去破解飞机降落和八皇后问题(轻松拿捏版)

引用

CSDN

https://m.blog.csdn.net/2401_82648291/article/details/144649025

本篇主题：解答洛谷的飞机降落和八皇后问题

制作日期：2024.12.23

隶属专栏：C/C++题海汇总

本篇简介：

通过基于深度优先算法的掌握下；对本篇引入的两道题目如何解答；为什么要这么做而展开的深入探讨，目的在于帮助读者理解这种算法要如何应用；怎么实际解答算法问题。

开篇前我们来普及一下深度优先遍历：

一、深度优先遍历（DFS）简介

深度优先遍历是一种图（包含树这种特殊图结构）的遍历策略。其核心思想是沿着图的某条路径尽可能深入地探索，直至无法继续前进，然后回溯到上一个节点，再尝试其他未探索过的分支路径，如此反复，直至遍历完所有节点。常用于解决诸如查找图的连通分量、判断图是否连通、在树中查找特定节点等诸多问题。

二·八皇后问题：

2.1题目叙述：

测试用例：

输入：6
输出：

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

洛谷原题链接： [USACO1.5] 八皇后 Checker Challenge - 洛谷

2.2思路简述：

当我们看到这个图的时候就不难想到应该是深度优先遍历走dfs了吧，也就是决策树解答（学过深度优先的话）；然后我们就往后面瞅瞅发现了数据范围：

因此更加明确了走暴力dfs来解决。

多说一点：这道题其实和我们某篇写的数独问题很像；或者也可以学习一下那道解法；当然细心的博主已经总结好博客了，欢迎阅读： 探究解数独问题-CSDN博客

下面我们画图解析一下：

这样就设计好我们的bool标记数组了，也方便我们后序的回溯和剪枝的使用。


bool col[14] = { false };
bool row[14] = { false };
bool main_diag[26] = { false};
bool sec_diag[27] = { false };

下面操作：

回溯：当我们都选完了；就要向上一层返回；然后再从当前层往后接着选择合适位置放棋子；此时就要把回去当前的位置标记取消变成false。

剪枝：当符合要求，也就是没有被标记过，就可以放棋子，但是也要给它标记一下；然后往下一层递归。

递归出口：也就是当我们走到的层数大于n；此时就可以把保存的结果也就是一行依次增大对应的可以放棋子的列数组放入我们要返回的ret的二维数组；这里虽然我们设计的dfs数组它是无返回值的；但是只有的当符合放旗子的要求才会进入下一层递归；那么当到达最后一层放完然后下一次递归到递归出口，此时返回肯定是有答案的了，因此只需要在递归出口设计返回即可。

这里博主设计的dfs函数用的是全局变量对这里记录当前行的变量就需要在进入递归以及回溯的时候还要进行处理；如果是作为函数参数，那么它可以利用函数的特性自己处理了，就不需要我们首手动操作了；因此如何设计看自己的想法。

2.3代码解答：


#include<bits/stdc++.h>
using namespace std;
int n;
bool col[14] = { false };
bool row[14] = { false };
bool main_diag[26] = { false};
bool sec_diag[27] = { false };
vector<vector<int>>v;
vector<int>path;
int pos = 1;
int ret = 0;
void  dfs() {
    if (pos > n) {
        if (v.size() < 3) v.push_back(path);
        ret++;
      return;
    }
    for (int j = 1; j <= n; j++) {
    if (col[j] || row[pos] || main_diag[j - pos + n] || sec_diag[j + pos]) continue;
     col[j] = row[pos] = main_diag[j - pos + n] = sec_diag[j + pos] = 1;
     pos++;
     path.push_back(j);
     dfs();
     pos--;
     path.pop_back();
     col[j] = row[pos] = main_diag[j - pos + n] = sec_diag[j + pos] = 0;

    }
}
int main() {
    cin >> n;
    dfs();
    for (int i = 0; i < v.size(); i++) {
        for (auto a : v[i])cout << a << " ";
        cout << endl;
    }
    cout << ret << endl;
    return 0;
}

最后也是过了：

三·飞机降落：

3.1题目叙述：

测试用例：

输入：

输出：

YES
NO

洛谷原题链接： [蓝桥杯 2023 省 B] 飞机降落 - 洛谷

3.2思路简述：

可能猛的一看还不能特别理解下面我们把题目介绍简化一下：

这里每个飞机都有三个参数分别是T，D，L。

T:飞机到来时候的时刻。

D:飞机到来后可以选择不降落，盘旋的最长时间。

L:飞机开始下降到完成所需的时间。

这时我们可以考虑把它整成一个飞机的结构体；用着也方便：

此外数据范围也是比较小的，为我们的暴力dfs提供了佐证：

飞机设计成结构体：


struct p{
    int T,D,L;
} parr[11];
int check[11]={0};

提示：这里当我们给飞机结构体输入数据的时候从1开始为了后面对check数组下标对应；以及对递归出口的处理更加方便；让数组下标与几号飞机对应更加形象。

这里我们可以看到每个飞机都有一个到达时刻；如果当前飞机完成下降后；此后当前时刻又会来到下一个时刻。

下面看一张图，更加明确它是如何进行的：

其实就是多次遍历这个数组（根据时刻判断是否可以下降；然后及时标记或者解除标记即可，当次数等于飞机架数就说明都完成了；直接向上次返回true即可）

当时这里我们就可以得出结论了；因为每次飞机到来都会有个时刻：也就是某个飞机要想下降它的时间范围就是T~T+D;因此我们考虑用当前时刻作为dfs参数；递归到下一层找下一个下降的飞机；当前时刻就要累加上上次下降的飞机；而到来的时刻传给下一层（也就是下一个飞机要想下降依据的时间）

这里疑问就是什么时候飞机可以下降：

首先先设计一下bool数组check用来记录是否飞机下降过了：这里默认初始化为0；也就是没有下降过；当发现它符合条件可以下；就把它标记成1；因此1就代表不能下降了。

分为两种情况：

1·到达的时刻也就是T小于当前的时间；那么此时它就要盘旋；盘旋到某个时间正好到达了当前时刻；就开始下落。

2·到达时刻比当前时刻小，就肯定可以降落。

3·此飞机没有下降过。

根据上面我们可以得出当check中某个飞机对应的下标是0同时某个飞机的T+D>=L就可以下降否则就不允许。

插：这里博主设计的dfs函数判断的是不合适的飞机就直接continue接着往后遍历其他合适的飞机判断，大家也可以设计合适的飞机走这个if：


 if(check[i]||parr[i].T+parr[i].D<curtime) continue;

然后就是时间是怎么变化的？

这里也分了两种情况：

1·如果此时飞机还没到来；那么时间就自己走；等它到来加上下架时间即T+L。

2·飞机已经在这之前到来了；那么就可以利用盘旋时间等到到达curtime在下降即：curtime+L。

因此可以发现这里取的是飞机到达时刻以及当前时刻的最大值进行累计max(T,curtime)+L。

这里我们dfs要不要返回值呢？

我们看到上面的dfs就是无返回值；因为它是把记录的数据放入返回数组，需要的是全部答案，因此需要我们对它都走一遍才能得出；而这道题它需要的只是一个能否完成下降；因此只要找到一种下降情况可以成立就返回true；上层接收到true接着返回；最后就yes了，不合适就false让上层知道然后更换选择；如果一直上返false不合适最后返回到第一次还是false最后就no了。

遍历之前的递归出口：检查是否越界；如果是的话也就是飞机一直选的可以下降的才会到达最后的递归出口；直接在最后返回true给上一层；也就是说明可以找到使它们都下降；因此要输出YES；只要dfs返回true我们就让它一直返回即可；当我们遍历飞机数组一圈都没找到可以下降的那么就返回false；说明上一个下降的飞机不能被选择。

剪枝：也就是只有符合那上述两个条件的飞机才可以走后面下降操作（后面也要处理bool数组标记1)。

回溯：如果下层返回当前层的是false就是当前层飞机不能下降；因此把它标记回0（说明它可能会在下层还是可以下降的）；然后for去往后遍历后面的飞机让它下降即可。

要点到这说的也就差不多了；此刻我们就可以ko这道飞机降落的深度优先搜索题咯。

小tip：这里由于题目给了多组测试飞机数组；因此博主这里觉得设置成全局的check数组更加方便用（可能是一个习惯啊，对暴搜类就这样）；因此每次搞完一组飞机数组要去下一组之前记得memset置0以下。

下面就开始我们的愉快代码环节：

3.3解答代码：


#include<bits/stdc++.h>
//此题就是决策树的深度递归去选择合适的方案；在画决策树就可以明白下一层
//需要的是上一层飞机降完的时刻（后面选的飞机就只能在这个时刻或者它之后
//下降了） 第一层就是0时刻的飞机下降，依次后面递归
using namespace std;
struct p {
    int T, D, L;
} parr[11];//飞机包含到达时间，最大盘旋时间，下降所需时间
int check[11] = { 0 };//标记此下标号飞机是否已经下降完了
//1:已经选择了停下的飞机  0：可以选择的飞机（但同时需要满足时间条件）
int n;
//dfs参数设计：一个是统计什么时候都停了返回；另一个记录当前时刻（因为
//每个飞机的T就是到达时刻）
bool dfs(int pos, int curtime) {
    if (pos > n) return 1;//满了就是飞机都停了向上层返回
    for (int i = 1; i <= n; i++) {
        //选择的是不符合的飞机直接跳过：（能在当前时间下降，则它要么比当前时间
        //晚到达，要么提前到达但是在盘旋；也就是对下面的关系式的解释）
        //但是还要确定此时check是0；
        if (check[i] || parr[i].T + parr[i].D < curtime) continue;
        check[i] = 1;
        //这就是要下降了：
        //下降完时间来到：有可能某飞机此刻提前来了，他要盘旋
        //等到到达当前时间开始下降；或者到此刻时间飞机还没到，还要等它到才下降
        //故下降时间完来到的时间是两者max值+下降用时
        if (dfs(pos + 1, max(curtime, parr[i].T) + parr[i].L))return 1;
        check[i] = 0;
    }
    return 0;
}
int main() {
    int N;
    cin >> N;
    while (N--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> parr[i].T >> parr[i].D >> parr[i].L;//从一开始
            //每个下标对应的几号飞机
        }
        memset(check, 0, sizeof(check));//因为标记数组是全局的，故每次
        //都要置零
        if (dfs(1, 0)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

当然了，怎么可能打脸；也是通过了：

四·深度优先算法基于本篇的总结：

这里博主根据做了一些关于深度优先搜索题的一下个人总结下面分享大家：

首先我们看到类似这样依次可以选择；然后选择一个后，我们又可以根据一些条件再次选择依次进行下去直到达到某个条件（说白了也就是可以画出决策树）

重点来啦：首先我们根据题目以及给的一些要求进行画图->决策树->进而根据画图可以得出何时剪枝，怎么回溯,递归出口是什么（转化成表达式）->然后根据树判断是否每层都需要控制的变量（确定是设置成函数参数还是全局变量）最终就构成了我们所需的dfs函数了当然，个人认为大多数这类的题都需要一个或者多个bool数组标记判断（这里根据我们题的题意判断是否需要）

最后其实完成dfs就是需要找好递归出口，剪枝，回溯，参数设计，返回值设计，接下来就大差不差完成了，稍微检查一下就ok咯！

本期有关深度优先搜索的分享就到此为止了，感谢大家的阅读，也希望对大家学习深度优先搜索解题方便有帮助，感谢支持！！！