T1. 漫漫回國路

2020 年 5 月，國際航班一票難求。一位在美國華盛頓的中國留學(xué)生，因為一些原因必須在本周內(nèi)回到北京?，F(xiàn)在已知各個機(jī)場之間的航班情況，求問他回不回得來（不考慮轉(zhuǎn)機(jī)次數(shù)和機(jī)票價格）。

時間限制：1 s
內(nèi)存限制：64 MB

• 輸入
  第一行為 case 個數(shù) $n(n<10)$。
  每一個 case，第一行為機(jī)場個數(shù) $N$，$N\le 10$。
  之后的 $N$ 行，每一行包含 $N$ 個整數(shù)。第 $i$（$1\le i\le N$）行的第 $j$（$1\le j\le N$）個整數(shù)代表從第 $i$ 個機(jī)場出發(fā)到第 $j$ 個機(jī)場的能買到的航班的最低票價 $t$（$0<t<10000$）。如果不幸沒有航班，那么用 $?1$ 表示。
  第 $i$ 行第 $i$ 個整數(shù)為 $0$。起點(diǎn)華盛頓杜勒斯國際機(jī)場的編號為 $1$，終點(diǎn)北京首都國際機(jī)場的編號為 $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
  

思路分析

此題考查搜索算法，屬于基礎(chǔ)題。

從起點(diǎn) $1$ 開始搜索，枚舉從當(dāng)前點(diǎn) $x$ 可以到達(dá)的任意點(diǎn) $i$，如果從 $x$ 到 $i$ 存在航班且尚未走過，就乘坐該航班到達(dá)點(diǎn) $i$，并從點(diǎn) $i$ 繼續(xù)搜索，直至走到盡頭或者終點(diǎn) $n$ 即可結(jié)束。用 $\mathtt{DFS}$ 或 $\mathtt{BFS}$ 均可實現(xiàn)。

/** 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())