題目連結:
題目大意:
給定兩正整數 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
本題只是單純的 BFS (廣度優先搜尋)即可達成要求。
從第 0 階開始,檢查其連接到哪些階層,將連結到的階層加進佇列(Queue)裡。然後再依序檢查佇列裡的那些階層各自連接到哪些其他的階層。而已經加進過佇列裡的階層便不必加入。
重複以上步驟,直到佇列裡的元素全部檢查完了,代表沒有方法從第 0 階到第 n 階;或著中途把第 n 階加入了佇列,代表有方法到第 n 階。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。