4. 飞机降落-dfs

4.飞机降落 - 蓝桥云课 (lanqiao.cn)

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct plane{
    int t,d,l;
}p[12];
int n;
//pan数组用来判断当前飞机降落了么，true代表降落了，false没降落
bool pan[12];
//cnt是已经降落的飞机个数，time是上一个降落的飞机的降落时间
bool dfs(int cnt,int time){
//    先判断一下如果已经降落了n个飞机
//    那么直接return行了，已经可以输出yes了
    if(cnt>=n)
        return true;
//    如果飞机还没降落完执行下面的,把n架飞机遍历一遍
    for(int i=0;i<n;i++){
//        先看看当前飞机降落了么，如果没降落 pan数组是false
//        false取反为true，执行下面代码
        if(!pan[i]){
//            先让pan数组为true，代表这个飞机降落了
            pan[i]=true;
//            如果飞机最晚降落时间在当前时间的前面
//            说明不符合要求，时间已经过去了
            if(p[i].t+p[i].d<time){
//                pan数组变成false回溯
                pan[i]=false;
                return false;
            }
//            说明符合要求，执行下面代码
//            计算一下当前飞机降落完是什么时候
            int t=max(time,p[i].t)+p[i].l;
//            递归调用
//            如果为if判断为true说明这条路能走下去，返回true
            if(dfs(cnt+1,t))
                return true;
//            否则，说明这条路不通，即当前飞机不能降落
//            应该让别的飞机先降落，然后这架飞机在后面再降落
//            所以需要回溯
            pan[i]=false;
        }
    }
//    如果一个true都不满足，则返回false，千万别忘了
    return false;
}
void solve(){
//    每组有n行飞机的数据
    cin>>n;
//    输入n行飞机的数据
    for(int i=0;i<n;i++)
        cin>>p[i].t>>p[i].d>>p[i].l;
    if(dfs(0,0))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
//    因为有t组每一组不相通
//    所以要把pan数组 置为初始值
    for(int i=0;i<n;i++)
        pan[i]=false;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //因为有t组
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}