前往
大廳
主題

ZeroJudge - f350: 五角星填數字 解題心得

Not In My Back Yard | 2021-11-24 00:00:08 | 巴幣 0 | 人氣 266

題目連結:


題目大意:
給定十個頂點編號為 A ~ J,點與點之間的連接關係如下圖所示:

現在要將 1 ~ 10 這 10 個數字依序填入這十個頂點之中(每個數字都必須被使用且不得重複填入),而每個區域之值將會是形成該區域之頂點之值總和。

輸入有多列,每列給定一個區域值(格式參見範例輸入),代表一個「條件」。試問有多少種方式可以將數字依序填入 A ~ J 之中,且每個區域之值符合給定的條件限制(如果無給定限制,則該區域值可為任意值)。請將所有可行的方法按照字典序輸出,而每個方法將會有 10 個數字,依序代表 A ~ J 填入的數字。



範例輸入:
範例輸入 #1
FBC = 13
GDE = 19
CAD = 12
HIF = 21
GEJ = 16

範例輸入 #2
FCB = 15
HIF = 15
DAE = 26
GED = 19
DCA = 20
HGJ = 9

範例輸入 #3
DGE = 10
FBC = 17
DEA = 17
HIF = 17
ADC = 20


範例輸出:
範例輸出 #1
1 6 3 8 2 4 9 7 10 5
1 6 3 8 2 4 9 10 7 5
1 6 3 8 9 4 2 7 10 5
1 6 3 8 9 4 2 10 7 5
3 6 5 4 7 2 8 9 10 1
3 6 5 4 7 2 8 10 9 1
3 6 5 4 8 2 7 9 10 1
3 6 5 4 8 2 7 10 9 1

範例輸出 #2
9 8 1 10 7 6 2 4 5 3
10 6 1 9 7 8 3 2 5 4
10 8 1 9 7 6 3 4 5 2

範例輸出 #3
8 4 10 2 7 3 1 5 9 6
8 4 10 2 7 3 1 9 5 6
8 9 5 7 2 3 1 4 10 6
8 9 5 7 2 3 1 10 4 6
9 3 10 1 7 4 2 5 8 6
9 3 10 1 7 4 2 8 5 6
9 4 10 1 7 3 2 6 8 5
9 4 10 1 7 3 2 8 6 5
9 5 4 7 1 8 2 3 6 10
9 5 4 7 1 8 2 6 3 10
9 10 4 7 1 3 2 6 8 5
9 10 4 7 1 3 2 8 6 5
10 5 4 6 1 8 3 2 7 9
10 5 4 6 1 8 3 7 2 9


解題思維:
就是單純地窮舉所有可能性即可,即利用深度優先搜尋(Depth First Search,DFS)的精神從 A 填到 J。

而我們可以將條件的「區域」按照字典序排序,例如 FCB = 15 會變成 BCF = 15 而 GDE = 19 變成 DEG = 19 等。這樣我們當我們填到某個頂點 X 時,我們只要檢查那些以 X 作為結尾的區域總和是否符合條件即可。




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

創作回應

更多創作