C语言 dfs算法 十四届蓝桥杯 D飞机降落问题

Question

题目：

打算用dfs算法写

#include<stdio.h>

int N;
const int n=11;
int T[n],D[n],L[n];
bool have_answer,used[n];  //used[n] 飞机是否降落过 

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}

void dfs(int x,int time)
{
    if(have_answer) return;
    if(x==N) 
    {
        have_answer=1;
        return;
    }
    for(int i=1;i<=N;++i)
    {
        if(!used[i]&&T[i]+D[i]>=time)
        used[i]=1; 
        dfs(x+1,max(T[i],time)+L[i]);
        if(have_answer) return;
        used[i]=0;
    }
}

void solve()
{
    have_answer=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d %d",&T[i],&D[i],&L[i]);
         used[i]=0;
    }
    dfs(0,0);
    if(have_answer) printf("YES\n");
    else printf("NO\n");
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

代码没有输出结果，帮忙找找错

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

题目描述：有N架飞机要陆续降落在同一个跑道，第i架飞机需要在时刻Ti开始降落，着陆时间为Li，降落后需要Di时间才能腾空，问是否存在一种降落顺序，使得所有飞机都能成功降落。 问题定位：代码没有输出结果，需要找出问题所在。 问题分析：

1. 程序逻辑分析： 该代码使用DFS深度优先搜索算法，考虑了一种情况下所有的飞机都能成功降落的情况。 核心函数dfs(x, time)：其中x是搜索到第x架飞机，time是当前时间。 首先，当搜索完所有的飞机时（即已经找到一种降落顺序），就可以输出“YES”并返回。 然后，遍历所有未被降落过的飞机，若当前飞机未被降落过并且能在当前时间降落，则标记该飞机已经降落并继续递归地搜索下一架可降落的飞机，然后再将该飞机的状态还原为未降落过，接着从其他飞机回溯时，可能又会搜索该飞机的次序。
2. 代码错误分析： a. 在程序的第3行 const int n = 11; 定义了一个常量 n, 在定义该常量是没有做特效处理， .因此，可以改成 const int n = 15;（根据样例最多只有15台飞机）。 b. 在函数 dfs(x, time) 的第13行代码 if(!used[i] && T[i]+D[i]>=time) 中，判断当前飞机是否可以降落的条件错误，应改成 if(!used[i] && T[i]>=time)，即当前飞机的降落时间必须晚于等于上一架飞机的腾空时间，而不是当前飞机的降落时间加腾空时间必须晚于上一架飞机的降落时间。 c. 在函数 dfs(x, time) 的第22行代码 dfs(x+1, max(T[i], time)+L[i]); 中，应该先递归dfs得出子结点，再进行回溯搜索，因此，在回溯回来时，应该还原T[i]，而不是时间time，所以应该改成 dfs(x+1, max(T[i], time)+L[i]);（即还原T[i]）。 d. 在函数 solve() 中，在输入飞机的信息后，应该使用 memset(used, 0, sizeof(used))初始化used数组，因为used数组的值在主函数中为多组测试数据时没有重新初始化，因此可能会对下一次测试造成影响。 问题解决： 根据上述错误分析，修改后的代码如下：