目录

题目

代码

AC结果

思路 

〇、例子

一、获取数据

二、深度优先遍历（DFS）

1.入参

2.出口

3.判断是否找到安全降落方案

4.递推过程

5.回溯过程

6.DFS完整代码

三、输出打印

题目

4957. 飞机降落 - AcWing题库https://www.acwing.com/problem/content/description/4960/

代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int T = input.nextInt();//数据组数for(int i = 0; i < T; i++) {int N = input.nextInt();//飞机数int[][] a = new int[N + 1][3];a[0][0] = 0;//Tia[0][1] = 0;//Dia[0][2] = 0;//Lifor(int j = 1; j < N + 1; j++) {a[j][0] = input.nextInt();a[j][1] = input.nextInt();a[j][2] = input.nextInt();}boolean[] state = new boolean[N + 1];//记录飞机降落状态boolean[] flag = new boolean[1]; flag[0] = false;//记录是否找到安全的降落方案dfs(0,state,flag,0,N,a);//输出打印if(flag[0]) {System.out.println("YES");}else {System.out.println("NO");}}}//深度优先搜索public static void dfs(int k,boolean state[],boolean[] flag,int t,int N,int a[][]) {  //t记录时刻//出口if(flag[0]) {return;}//判断是否为可行方案if(k == N) {flag[0] = true;}for(int i = 1; i < state.length; i++) {if(!state[i]) {//第i架飞机没有降落int tempt = t;if(t <= a[i][0] + a[i][1]) {//可以降落state[i] = true;if(t < a[i][0]) {//等飞机到了再降落t = a[i][0] + a[i][2];}else {//a[i][0] < t < a[i][0] + a[i][1]  飞机已经到了，直接降落t = t + a[i][2];}}else{//t > a[i][0] + a[i][1]->炸了return;}dfs(k+1,state,flag,t,N,a);//恢复state[i] = false;t = tempt;}}}
}

AC结果

思路 

这道题的解题思路的本质就是枚举，将所有可能降落的顺序都枚举一遍，判断在所有的方案中，是否存在一个安全的降落方案。利用深度优先搜索（DFS）实现上述想法，将所有降落顺序按照树的形式排列，然后采取深度优先对树进行遍历。利用一个boolean类型的flag记录是否找到安全降落的方案，若有则将其值改为true，否则为flase。最后，每一组数据根据flag的值输出“YES”或“NO”即可。

〇、例子

 以下面这组数据为例。有3架飞机，一共有6种可能的降落方案，接着一一判断是否可行。

1-2-3不可行

1-3-2不可行

2-1-3不可行

2-3-1不可行

3-1-2不可行

3-2-1可行

所以输出“YES”

1
3
0 100 10
10 10 10
0 2 20

一、获取数据

T表示数据组数；

N为某组中的飞机数；

a[i][0]为Ti，表示该组第i架飞机到达机场的时刻；

a[i][1]为Di，表示该组第i架飞机到达机场后可盘旋的时间；

a[i][0]为Li，表示该组第i架飞机降落所需耗时；

state记录第i架飞机的降落状态（是否已降落）；

flag记录是否找到可行的安全降落方案；

		Scanner input = new Scanner(System.in);int T = input.nextInt();//数据组数for(int i = 0; i < T; i++) {int N = input.nextInt();//飞机数int[][] a = new int[N + 1][3];a[0][0] = 0;//Tia[0][1] = 0;//Dia[0][2] = 0;//Lifor(int j = 1; j < N + 1; j++) {a[j][0] = input.nextInt();a[j][1] = input.nextInt();a[j][2] = input.nextInt();}boolean[] state = new boolean[N + 1];//记录飞机降落状态boolean[] flag = new boolean[1]; flag[0] = false;//记录是否找到安全的降落方案

二、深度优先遍历（DFS）

1.入参

public static void dfs(int k,boolean state[],boolean[] flag,int t,int N,int a[][]) { 

k表示已经降落的飞机数；

state数组表示各个飞机的降落状态；

flag[0]记录是否已经找到安全的降落方案；

t表示当前时刻；

N表示该组共有的飞机数；

a数组是一个三维数组，分别记录了每架飞机的到场时刻，可盘旋时间和降落耗时；

2.出口

		//出口if(flag[0]) {return;}

当flag[0]为true时，一路回溯即可。

3.判断是否找到安全降落方案

		//判断是否为可行方案if(k == N) {flag[0] = true;}

当已降落飞机数k等于该组飞机总数N时，即代表已经找到了安全可行的降落方案。

4.递推过程

		for(int i = 1; i < state.length; i++) {if(!state[i]) {//第i架飞机没有降落int tempt = t;if(t <= a[i][0] + a[i][1]) {//可以降落state[i] = true;if(t < a[i][0]) {//等飞机到了再降落t = a[i][0] + a[i][2];}else {//a[i][0] < t < a[i][0] + a[i][1]  飞机已经到了，直接降落t = t + a[i][2];}}else{//t > a[i][0] + a[i][1]->炸了return;}dfs(k+1,state,flag,t,N,a);

遍历state数组，找到哪一架飞机尚未降落。需要用一个tempt变量记录，当前时刻，一边后续回溯时使用。然后判断当前时刻t是否小于等于t <= a[i][0] + a[i][1]（飞机到场时刻+余油可盘旋时间=最迟降落时刻），若满足则表示这架飞机是可以降落的（具体细分为两种情况），若不满足则这架飞机得坠机，因此这个方案不可行需要return回溯。

如果经过上述判断，确定该架飞机可以降落，有两种情况：

（1）t<a[i][0]，即当前时刻小于该架飞机到场时刻。说人话就是，飞机还没飞到机场，得等飞机到机场才能开始降落。

（2）a[i][0] <= t < a[i][0] + a[i][1]，当前时刻在飞机可降落的范围之内。说人话，上一架飞机完成降落，下一架飞机可以马上接着进行降落。

若当前飞机可以降落，可以再调用dfs方法，进行下一层的递推判断。若存在安全可行的降落方案，将在递推的过程中产生并判断出来。

5.回溯过程

如果当前的降落方案不可行，飞机炸了，则需要回溯到上一层选择其他降落顺序。回溯到上一层之前，需要将以下变量恢复，state[i]需要恢复为false（表示第i架飞机并没有完成降落），时间也将倒流回到tempt时刻。

6.DFS完整代码

	//深度优先搜索public static void dfs(int k,boolean state[],boolean[] flag,int t,int N,int a[][]) {  //t记录时刻//出口if(flag[0]) {return;}//判断是否为可行方案if(k == N) {flag[0] = true;}for(int i = 1; i < state.length; i++) {if(!state[i]) {//第i架飞机没有降落int tempt = t;if(t <= a[i][0] + a[i][1]) {//可以降落state[i] = true;if(t < a[i][0]) {//等飞机到了再降落t = a[i][0] + a[i][2];}else {//a[i][0] < t < a[i][0] + a[i][1]  飞机已经到了，直接降落t = t + a[i][2];}}else{//t > a[i][0] + a[i][1]->炸了return;}dfs(k+1,state,flag,t,N,a);//恢复state[i] = false;t = tempt;}}}

三、输出打印

根据flag[0]的值可以知道是否找到安全降落的方案，然后对应输出“YES”和“NO”即可。

			//输出打印if(flag[0]) {System.out.println("YES");}else {System.out.println("NO");}