ZeroJudge A219: Limit Arrangement

Kogaru's DFS pruning technique has improved a bit over this summer, but he still can't get past the nightmare of Dynamic Programming (DP). Now you're given N people, labeled A, B, ..., Z, and there's always someone who doesn't want to be in a certain position. Please list all possible arrangements, but the output file can easily become too large! So, if the new arrangement has the same parts as the previous one, only output the different parts.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
There are multiple test cases. For each test case, the first line contains a positive integer N (1 ≤ N ≤ 15). The following N lines represent the positions that the Nth person does not want to be in, with 0 indicating the end of the list.Please list all possible arrangements (in lexicographical order). If parts of the arrangement are the same as the previous one, do not output them again—only output the different parts.
3
0
0
0
3
1 0
3 0
0		ABC
CB
BAC
CA
CAB
BA

BAC
CA
CB

Thought Process

Use a two-dimensional array of boolean values to record which positions each person does not want to be placed in, and use DFS to find all possible arrangements. When outputting, keep track of the previous string to be outputted and compare it with the current string. Skip over any characters that are the same. The strings being recorded are complete and uncut strings.

Sample Code－ZeroJudge A219: Limit Arrangement

#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
Tags

Related Posts

Comments