2020 年 12 月青少年软编等考 C 语言五级真题解析

T1. 漫漫回国路

2020 年 5 月，国际航班一票难求。一位在美国华盛顿的中国留学生，因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况，求问他回不回得来（不考虑转机次数和机票价格）。

时间限制：1 s
内存限制：64 MB

• 输入
  第一行为 case 个数 $n(n<10)$。每一个 case，第一行为机场个数 $N$，$N\le 10$。之后的 $N$ 行，每一行包含 $N$ 个整数。第 $i$（$1\le i\le N$）行的第 $j$（$1\le j\le N$）个整数代表从第 $i$ 个机场出发到第 $j$ 个机场的能买到的航班的最低票价 $t$（$0<t<10000$）。如果不幸没有航班，那么用 $-1$ 表示。第 $i$ 行第 $i$ 个整数为 $0$。起点华盛顿杜勒斯国际机场的编号为 $1$，终点北京首都国际机场的编号为 $N$。
• 输出
  每一个 case 一行。能够回国，输出字符串 YES。如果无法回国，输出字符串 NO。
• 样例输入

  2
  3
  0 100 -1
  -1 0 200
  -1 -1 0
  4
  0 1 5 -1
  3 0 1 -1
  2 4 0 -1
  4 1 1 0
  

• 样例输出

  YES
  NO
  

思路分析

此题考查搜索算法，属于基础题。

从起点 $1$ 开始搜索，枚举从当前点 $x$ 可以到达的任意点 $i$，如果从 $x$ 到 $i$ 存在航班且尚未走过，就乘坐该航班到达点 $i$，并从点 $i$ 继续搜索，直至走到尽头或者终点 $n$ 即可结束。用 $\mathtt{DFS}$ 或 $\mathtt{BFS}$ 均可实现。

/** Name: T1.cpp* Problem: 漫漫回国路* Author: Teacher Gao.* Date&Time: 2025/01/03 00:21*/#include <iostream>
#include <queue>using namespace std;bool bfs(int n, int a[][15])
{queue<int> Q;bool f[15][15] = {0};Q.push(1);while (!Q.empty()) {