題目連結:
有一個房子形狀的圖,將節點編號為如下:
(請無視圖中的箭頭,這個圖是無向圖(雙向邊))
請從節點 1 開始試著走過所有的邊(即一筆畫畫過此圖),把所有的解法按照字典序輸出。
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)且要從字典序小的開始找連向其他節點的邊。然後紀錄遞迴時的路徑,並在所有邊都走完、沒得走之後輸出該內容(此時也是遞迴的停止條件,要回到上一層的遞迴堆疊)。
整個遞迴跑完之後,期間輸出的內容即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。