1239 . 最終兵器X

題解  |  Anpig  |  2020-11-27  |  1k  |  4 Minutes

題目

西元 2185 年，地球人終於有能力征服其他有生物的星球，
不過卻受到該星球生物的反擊。於是科學家們發明了一種「最終兵器 X」，
它能自動攻擊左上、上、右上、右、右下、下、左下、左等八個方向的敵人，
只要在地圖上放上幾台，就可以不費吹灰之力消滅敵人。

輸入說明

輸入第一行會有一個正整數 T，表示總共有幾筆測資。
每筆測資有一個正整數 N (4<=N<=12)，代表要放 N 台的最終兵器 X。

輸出說明

針對每筆輸入請輸出每種可能的排法，因為每列只能放一個，
故只要輸出每列的最終兵器 X 是放在第幾行就可以了，
請依序輸出第一列、第二列、…第 N 列的位置。
順序越前面數字越小越好。

想法

這題其實就是把八皇后變成 N 皇后。

我們可以先開一個陣列int queen[15];，
存放「每一列」要在「哪一欄」放皇后，
因此哪一列就是陣列的 index，
而在該 index 的值就是指在那一列的哪一欄放皇后。
（這個部分其實輸出說明算是有提示到）

再來開始建造遞迴函數。

1
2
3
4
5
6
7
8
void solve(int n) {
    for (int i = 0; i < N; i++) {
        if (conflict(n, i) == 1) continue;
        queen[n] = i;
        solve(n + 1);
    }
    return;
}

我遞迴的想法是：
solve(n)代表現在要放第n個皇后了。
先不管會被其他皇后吃掉的情形，
我們有N個位置可以放皇后（0 ~ N - 1），
所以先放一個for迴圈，
到迴圈裡面再判斷該位置能不能放皇后，
如果可以的話，就紀錄那個位置，
也就是第n個皇后（第n列）放在第i欄，
寫作queen[n] = i;。

記錄下來之後我們就可以開始考慮放下一個皇后，
所以呼叫solve(n + 1);。

現在回到判斷格子能不能放的問題。

1
2
3
4
5
6
7
int conflict(int n, int t) {
    for (int i = 0; i < n; i++) {
        if (t == queen[i]) return 1;
        if ((n - i) == (t - queen[i])|| (n - i) == (t - queen[i]) * -1) return 1;
    }
    return 0;
}

這個conflict函數的參數n, t，
其實可以理解為棋盤的 x 和 y，
或是說第n個皇后放在第t欄；

而它的回傳值是0或1
（其實它是個布林值，只是我懶得include）：
0代表第n個皇后可以放在第t欄；
1代表第n個皇后不能放在第t欄。

先來一個for迴圈，
因為要和先前放的所有皇后比較。

第三行的if (t == queen[i]) return 1;，
是要看它和第i個皇后會不會位在同一欄
（由於我們宣告queen[]的想法已經不會讓皇后位在同一列了，
所以不需要再另外判斷皇后會不會在同一列）。

第四行的(n - i)和(t - queen[i])
可以理解為 x 和 y 的位移，當它們的絕對值一樣，
代表它們位在同一條斜線上。

最後回到solve函數，
當我們遞迴到solve(N)時就代表已經放完棋子了
（因為棋子會在第0到N - 1列），
該停止了，不然會一直遞迴下去。
所以加上 2 ~ 8 這幾行，讓它輸出，就完成這題了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(int n) {
    if (n == N) {
        for (int i = 0; i < N; i++) {
            printf("%d ", queen[i] + 1);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < N; i++) {
        if (conflict(n, i) == 1) continue;
        queen[n] = i;
        solve(n + 1);
    }
    return;
}

完整程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
int T, N;
int queen[15];
int conflict(int n, int t) {
    for (int i = 0; i < n; i++) {
        if (t == queen[i]) return 1;
        if ((n - i) == (t - queen[i])|| (n - i) == (t - queen[i]) * -1) return 1;
    }
    return 0;
}
void solve(int n) {
    if (n == N) {
        for (int i = 0; i < N; i++) {
            printf("%d ", queen[i] + 1);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < N; i++) {
        if (conflict(n, i) == 1) continue;
        queen[n] = i;
        solve(n + 1);
    }
    return;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        solve(0);
    }
    return 0;
}
tags:  #Formosa OJ #遞迴 #八皇后
全部展開 回到頂部 移至底部