切換
舊版
前往
大廳
主題

ZeroJudge - a280: 小朋友上樓梯 解題心得

Not In My Back Yard | 2019-05-11 22:59:13 | 巴幣 0 | 人氣 118

題目連結:


題目大意:
給定兩正整數 n 、 k (0 < n ≦ 100, k ≦ 10, 000),代表有一個小朋友一開始在第 0 階樓梯,他想要到第 n 階。而每個樓梯有各自可以傳送到的階層。

接著的 k 列輸入,每列給定兩正整數 a 、 b (0 ≦ a 、 b ≦ 100),代表第 a 階可以傳送到第 b 階(反過來是不行的)。

試問此位小朋友是否可以從第 0 階傳送到第 n 階。可以的話,輸出「OK!」;反之,輸出「Impossib1e!」。



範例輸入:
5 6
0 4
0 7
4 9
7 3
7 8
3 5

5 6
0 4
0 7
4 9
7 0
7 8
3 5


範例輸出:
Ok!
Impossib1e!


解題思維:
本題只是單純的 BFS (廣度優先搜尋)即可達成要求。

從第 0 階開始,檢查其連接到哪些階層,將連結到的階層加進佇列(Queue)裡。然後再依序檢查佇列裡的那些階層各自連接到哪些其他的階層。而已經加進過佇列裡的階層便不必加入。

重複以上步驟,直到佇列裡的元素全部檢查完了,代表沒有方法從第 0 階到第 n 階;或著中途把第 n 階加入了佇列,代表有方法到第 n 階。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作