ZeroJudge A219: 限制排列

小光的 DFS 剪枝技巧在這個暑假進步了一些些，但是仍然無法通過 DP 的噩夢。現在給你 N 個人，編號分別是 A、B、…、Z，接著總是會有人不想排哪裡，請你把所有可能列出來，但是輸出檔隨便生一生就爆表了！因此希望你如果新的排列跟上次一樣的部分就不輸出了，僅僅輸出不同的部分。

範例測資

範例輸入範例輸出
有多筆測資，每筆第一行有一個正整數 N (1 ≦ N ≦ 15)。接下來會有 N 行，第 N 行代表 第 N 個人不想排的位置，以 0 代表結束。請把所有可能列出來(依照字典順序)，跟上次一樣的部分就不輸出，僅僅輸出不同的部分。
3
0
0
0
3
1 0
3 0
0		ABC
CB
BAC
CA
CAB
BA

BAC
CA
CB

解題思路

使用二維陣列的布林值來紀錄每一個人不想要被排在哪裡，並且使用 DFS 來找出所有的可能性。在輸出時，紀錄上一個要輸出的字串，和目前的字串做比對，只要有相同的字元就跳過，被記錄的字串都是完整未刪減的字串。

範例程式碼－ZeroJudge A219: 限制排列

#include <iostream>
using namespace std;

bool MAP[30][30] = {};
int arr[26];
int N, used[30] = {}, add[30] = {};

void DFS(const int set) {
    if (set == N) {
        for (int i = 0; i<set; i++) {
            if(arr[i] == add[i]){
                continue;
            }
            arr[i] = add[i];
            cout << char('A'+ add[i]);
        }
        cout << "\n";
        return;
    }
    for (int i = 0; i<N; i++) {
        if (used[i] > 0 || MAP[i][set+1]) continue;
        add[set] = i;
        used[i]++;
        DFS(set+1);
        used[i]--;
        add[set] = -1;

    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i<26; i++) {
        used[i] = 0;
        add[i] = -1;
    }
    while (cin >> N) {
        for (int i = 0; i<26; i++) {
            for (int j = 0; j<26; j++) {
                MAP[i][j] = false;
            }
        }
        for (int i = 0; i<N; i++) {
            int num;
            arr[i] = -1;
            while (cin >> num && num != 0) MAP[i][num] = true;
        }
        DFS(0);
    }
}

//ZeroJudge A219
//Dr. SeanXD
標籤

相關文章

發佈留言