UVa 225 Golygons

Run Time: 1.440s
Ranking: 24/34

做了這道題目，才知道golygon是什麼意思，算是學到一個新字彙！下圖就是一個golygon：

 

從小紅點開始，往北走 1 步，再往東走 2 步，再往南走 3 步，……，就形成一個封閉的多邊形，而這個多邊形就是golygon。每次轉彎都是「直角」，每次轉彎之後都多走一步；轉折點不能重複，且最後一步必須要回到起點。

題目會告訴我們坐標平面上有哪些位置是「不能經過」的（也就是有一些座標被放了障礙物，不能通過）。我們要從原點 (0, 0)出發，不踩到任何障礙物，儘可能繞出一個golygon來。

上圖是一個「n = 8」的golygon，從紅點開始，形成golygon的路徑可以用英文字母描述成“neswswne”（go north, and then go east, and then go west, ...etc.）。本題要算出「所有可能的路徑」。舉例來說，當 n = 8，且平面上沒有任何障礙物的話，答案如下：

enwswsen
eswnwnes
neswswne
nwsesenw
senwnwse
swnenesw
wneseswn
wsenenws
Found 8 golygon(s).

顯然這是一道搜索題！也許是我沒什麼在剪枝，所以執行速度就有點差強人意...Q_Q 執行時間的排名是34個人當中的第24名。平常我總是要求自己執行時間至少要達到前50%，看來這題還有一些努力的空間囉！另外也要感謝和我一起討論的 Peter Yu 同學。:)