切換
舊版
前往
大廳
主題

ZeroJudge - c139: 00291 - The House Of Santa Claus 解題心得

Not In My Back Yard | 2019-09-29 22:44:47 | 巴幣 2 | 人氣 234

題目連結:


題目大意:
有一個房子形狀的圖,將節點編號為如下:
(請無視圖中的箭頭,這個圖是無向圖(雙向邊))

請從節點 1 開始試著走過所有的邊(即一筆畫畫過此圖),把所有的解法按照字典序輸出。



範例輸入:
No input


範例輸出:
123153452
123154352
154352312


解題思維:
把 8 條邊的資訊用一二維布林陣列存起來(因為是雙向邊,所以兩個索引值交換後仍應互通),即:
節點 1 和節點 2 互通、
節點 1 和節點 3 互通、
節點 1 和節點 5 互通、
節點 2 和節點 3 互通、
節點 2 和節點 5 互通、
節點 3 和節點 4 互通、
節點 3 和節點 5 互通、
節點 4 和節點 5 互通。

接著,從節點 1 開始深度優先搜尋(Depth First Search,DFS)且要從字典序小的開始找連向其他節點的邊。然後紀錄遞迴時的路徑,並在所有邊都走完、沒得走之後輸出該內容(此時也是遞迴的停止條件,要回到上一層的遞迴堆疊)。

整個遞迴跑完之後,期間輸出的內容即是所求。

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

創作回應

更多創作