前往
大廳
主題

ZeroJudge - d324: 00750 - 8 Queens Chess Problem 解題心得

Not In My Back Yard | 2021-06-02 00:00:05 | 巴幣 0 | 人氣 197

題目連結:


題目大意:
輸入第一列給定一個整數,代表有多少筆測試資料,每筆佔一列。緊接著有一個空白列,再接著才是測試資料們,每筆之間以一列空白列隔開。

每筆測資給定兩正整數 R 、 C,代表有一個皇后放在第幾列、第幾行(最左上為 (1, 1))。試問在 8 × 8 的棋盤上放 8 個皇后,使得皇后們彼此無法互相攻擊。在這樣的狀況下有多少版面有一個皇后是放在 (R, C) 的。

對於每筆測資先輸出標頭(參見範例輸出),代表行數統一在最上方,接著就是輸出每個版面每個皇后所在的列數。例如範例輸出的
SOLN       COLUMN
#      1 2 3 4 5 6 7 8

1      1 5 8 6 3 7 2 4
2      1 6 8 3 7 4 2 5
3      1 7 4 6 8 2 5 3
4      1 7 5 8 2 4 6 3
編號 2 代表有一個皇后放在 (1, 1) 、 (6, 2) 、 (8, 3) 、 (3, 4) 、 (7, 5) 、 (4, 6) 、 (2, 7) 、 (5, 8) 這八個位置(也就是依照行數由小排到大,然後移除掉行數的資訊(因為統一表示在標頭))。每個版面依據所剩的 8 個皇后列數之序列按照字典序由小到大排列並依據編號。

每筆測資的輸出之間空一列空白列。



範例輸入:
1

1 1


範例輸出:
SOLN       COLUMN
#      1 2 3 4 5 6 7 8

1      1 5 8 6 3 7 2 4
2      1 6 8 3 7 4 2 5
3      1 7 4 6 8 2 5 3
4      1 7 5 8 2 4 6 3


解題思維:
先利用這題的想法將 8 皇后問題的所有可能版面建成表格查詢。

接著對於每個給定的 (R, C) 掃過所有 8 皇后的所有版面,把所有在 (R, C) 有著皇后的版面過濾出來。然後將這些版面每個獨自將其皇后所在的列數擷取出來變成一個數列(記得依照行數由小排到大)。

再來將每個版面的數列按照字典序排列後編號並輸出即可。




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

創作回應

更多創作