切換
舊版
前往
大廳
主題

ZeroJudge - e880: Q1 合影隊形　解題心得

Not In My Back Yard | 2020-03-10 00:18:17 | 巴幣 2 | 人氣 179
題目連結：
題目大意：
輸入第一列給定一正整數 N （N ≦ 15），代表有 N 位球員。第二列給定另一正整數 M （M ≦ 50），代表有 M 對的球員彼此之間有一些摩擦。接著有 M 列輸入，每列給定兩個字元，代表兩名球員的編號（編號從 A 開始）以及代表他們之間有摩擦。

請找到一個字典序中最小的可能隊伍排列，使得彼此有摩擦的隊員不會排在相鄰位置。如果有責輸出該組解；反之，輸出「No Solution」。

範例輸入：
範例輸入一:
5
2
A B
C D

範例輸入二:
4
4
A B
C D
C A
C B
範例輸出：
範例輸出一:
ACBDE

範例輸出二:
No Solution
解題思維：
先將隊員之間的摩擦關係用一個二維布林陣列表示。例如 D[i][j] 、 D[j][i]，皆代表 i 、 j 隊員之間的關係。（弄成雙向的比較方便）

使用深度優先搜尋（Depth First Search，DFS）去找出每一組可能的排列。但是在遞迴到要取下一位隊員前，可以用上面提及的布林陣列判斷一下上一位跟現在挑的這位是否有摩擦。有的話就跳過該隊員，而不是挑該隊員並遞迴下去。

而且找到一解之後便可以直接用一變數表示，表示不須再找其他的解，進而快速跳出遞迴。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#深度優先搜尋（Depth First Search）
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

更多創作

追蹤 創作集
其他創作
作品資料夾