蓝桥杯实战题目解析：飞机降落问题的DFS算法实现
最编程
2024-02-04 16:53:51
...
//飞机降落： 暴力枚举DFS
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10 + 20;
struct plane{
int t, d, l;
}p[N];
bool st[N];//判断当前飞机是否已经降落
int n;//飞机个数。
//u表示已经有U架飞机成功降落了。
//time表示当前的时间,前一架飞机落地的时间。
bool dfs(int u, int time)
{
if(u >= n)
return true;
//考虑第（u + 1）架飞机谁落。
for(int i = 0; i < n; i ++)
{
if(!st[i])
{
st[i] = true;
if(p[i].t + p[i].d < time)
{
//回溯，回溯到DFS之前的状态。
st[i] = false;
return false;
}
int t = max(time, p[i].t) + p[i].l;
if(dfs(u + 1, t))
return true;
//回溯，回溯到DFS之前的状态。
st[i] = false;
}
}
return false;
}
void solve()
{
cin >> 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;
for(int i = 0; i < n; i ++)
st[i] = false;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while(t--)
solve();
}