[蓝桥杯] 飞机降落（C语言）_蓝桥杯飞机降落c语言

        题目链接

        [蓝桥杯 2023 省 B] 飞机降落 - 洛谷

        题目理解

        给定n个飞机的降落时间段，每个飞机有一个最早降落时间和最晚降落时间。飞机需要在指定的时间段内降落，并且每个飞机的降落时间是固定的。现在需要判断是否存在一种降落顺序，使得所有飞机都能在规定的时间段内降落。

        解题思路

        这是一个典型的回溯算法问题。我们可以使用深度优先搜索（DFS）来解决。

具体步骤如下：

1. 定义一个结构体Node，用于存储飞机的最早降落时间、最晚降落时间和降落需要的时间。
2. 定义全局变量t表示测试用例的数量，n表示飞机的数量，vis数组用于标记飞机是否已经降落，flag表示是否存在一种降落顺序。
3. 实现dfs函数，该函数用于进行深度优先搜索。参数deep表示当前搜索的深度，now表示当前时间。
4. 在dfs函数中，首先判断是否已经搜索到了所有飞机（即deep == n），如果是，则将flag置为true，表示存在一种降落顺序，然后返回。
5. 在dfs函数中，使用循环遍历所有飞机，对于每个飞机，判断是否已经降落（即0==vis[i]）以及飞机的最晚降落时间是否早于当前时间（即fj[i].r < now）。如果满足这两个条件中任一，则该顺序不能完成所有飞机的降落，进行剪枝，直接返回。
6. 在dfs函数中，如果飞机未降落且最晚降落时间不早于当前时间，将该飞机标记为已降落（vis[i] = 1），然后根据飞机的最早降落时间和当前时间，计算下一个飞机的降落时间，并递归调用dfs函数。
7. 在递归调用dfs函数之后，需要取消对当前飞机的标记（vis[i] = 0），以便进行下一次搜索。
8. 在主函数中，读取测试用例的数量t，然后循环读取每个测试用例的飞机数量n和飞机的降落时间信息。对于每个测试用例，先将flag置为false，然后遍历每个飞机，将其标记为已降落，并调用dfs函数进行搜索。最后根据flag的值输出结果。

完整代码（详解注释版）

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
struct Node 
{
    int l; // 飞机最早能降落的时间
    int r; // 飞机最晚能降落的时间
    int t; // 飞机降落需要的时间
};
 
int t, n, vis[15]; // t表示测试用例的数量，n表示飞机的数量，vis数组用于标记飞机是否已经降落
bool flag; // 是否存在一种降落顺序
struct Node fj[15]; // 存储飞机的降落时间信息
 
void dfs(int deep, int now) // 深度优先搜索函数，now表示当前时间
{ 
    if (deep == n) // 如果已经搜索到了所有飞机，将flag置为true，表示存在一种降落顺序
	{ 
        flag = true;
        return; 
    }
    for (int i = 1; i <= n; i++) 
	{
		if(vis[i]==1)//如果飞机已经降落，直接跳过向下进行
		{
			continue;
		}
        if (fj[i].r < now)
		{
			return; // 如果飞机的最晚降落时间早于当前时间，进行剪枝，直接返回
		}
        if (0==vis[i] && fj[i].r >= now) 
		{
            vis[i] = 1; // 标记该飞机已经降落
            if (fj[i].l > now)
			{
				dfs(deep + 1, fj[i].l + fj[i].t); // 如果飞机的最早降落时间比当前时间晚，计算下一个飞机的降落时间为最早降落时间加上降落需要的时间
			}
            else
			{
				dfs(deep + 1, now + fj[i].t); // 否则，计算下一个飞机的降落时间为当前时间加上降落需要的时间
			}
            vis[i] = 0; // 取消对当前飞机的标记，以便进行下一次搜索
        }
    }
}
 
int main() 
{
    scanf("%d", &t); // 读取测试用例的数量
    memset(vis, 0, sizeof(vis)); // 初始化vis数组为0
    while (t--) 
	{
        scanf("%d", &n); // 读取飞机的数量
        flag = false; // 初始化flag为false
        int k;
        for (int i = 1; i <= n; i++) 
		{
            scanf("%d %d %d", &fj[i].l, &k, &fj[i].t); // 读取每个飞机的降落时间信息
            fj[i].r = fj[i].l + k; // 计算飞机的最晚降落时间
        }
        for (int i = 1; i <= n; i++) 
		{
            vis[i] = 1; // 将飞机标记为已降落
            dfs(1, fj[i].l + fj[i].t); // 调用dfs函数进行搜索
            vis[i] = 0; // 取消对当前飞机的标记，以便进行下一次搜索
        }
        if (flag) printf("YES\n"); // 根据flag的值输出结果
        else printf("NO\n");
    }
    return 0;
}

————（如有问题，欢迎评论区提问）————