「你到底有沒有想過你以後要做什麼?你有目標嗎?你有夢想嗎?????????」「趕快醒醒好不好?別把自己的人生玩掉了。手機手機手機,你的人生到底還剩下什麼?」
嘉嘉和阿偉曾經是最好的朋友,他們一起練習程式,一起吃拉麵,一起過著資工的生活。因為一次的爭執,兩人反目成仇,並誓言從此之後走自己的路。為了讓他們找回消失的友誼,小翊決定邀請他們一起玩桌遊—「第三次領地危機」。
遊戲盤由 $N \times M$ 的二維表格組成,每行由上到下以 $1$ 到 $N$ 的正整數編號,每列由左到右以 $1$ 到 $M$ 的正整數編號,第 $x$ 行第 $y$ 列的格子以 $(x, y)$ 表示。在遊戲開始時嘉嘉位於 $(x_A, y_A)$,阿偉位於 $(x_C, y_C)$;而他們的目標為規劃一條路徑到各自的終點,其中嘉嘉的終點為 $(x_B, y_B)$,阿偉的終點為 $(x_D, y_D)$。
設 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$ 為某位玩家規劃的路徑,則其必須符合以下條件:
為了貫徹當初的誓言,他們打算「走自己的路」,兩人的路徑上不會有任何相同的格子。也就是說,設嘉嘉的路徑為 $P_1, P_2, \ldots$,阿偉的路徑為 $Q_1, Q_2, \ldots$,對於任意 $i, j$ 皆符合 $P_i \ne Q_j$。嘉嘉和阿偉發現,小翊可以指定一些起始點與終點破壞他們的計畫,讓他們沒辦法遵守誓言。聰明的你請寫一支程式,幫嘉嘉和阿偉判斷是否存在路徑使得他們能繼續「走自己的路」。
輸入的第一行為一整數 $T$,表示測資的數量。
每筆測資一行,包含十個正整數 $N$, $M$, $x_A$, $y_A$, $x_B$, $y_B$, $x_C$, $y_C$, $x_D$, $y_D$,分別表示地圖長寬與 $A$, $B$, $C$, $D$ 的位置。
對於每筆測資輸出一行,若嘉嘉和阿偉能「走自己的路」,請輸出 Yes
;否則,輸出 No
。
範例測資中,第一筆測資兩人可規劃的其中一種路徑如下圖:
第二筆測資中,兩人無法規劃出沒有相同格子的兩條路徑。
IOICamp 2022 Day5 pN
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 0~49 | 無額外限制 | 100 |