#include <stdio.h>
#include <stdbool.h>
#define NUM_PLACES 4
// 回溯函数：尝试构建所有可能的路径组合，A 总是紧跟 B
void backtrack(int *path, bool used[NUM_PLACES], int step)
{
    if (step >= NUM_PLACES)
    { // 边界条件：当步骤数等于地点数时打印路径
        for (int i = 0; i < NUM_PLACES; ++i)
            printf("%c", 'A' + path[i]);
        printf("\n");
        return;
    }
    // 如果还有足够的空间，尝试放置 A 和 B 作为一对
    if (step + 1 < NUM_PLACES && !used[0] && !used[1]) {
        path[step] = 0;     // 放置 A
        path[step + 1] = 1; // 放置 B
        used[0] = used[1] = true;
        backtrack(path, used, step + 2);
        used[0] = used[1] = false;
    } 
    // 尝试放置 C 或 D
    for (int i = 2; i < NUM_PLACES; ++i)  {
        if (!used[i])  {
            path[step] = i;
            used[i] = true;
            backtrack(path, used, step + 1);
            used[i] = false;
        }
    }
}

int main(){
    int path[NUM_PLACES];
    bool used[NUM_PLACES] = {false}; 
    // 开始回溯，从一个空路径开始
    backtrack(path, used, 0); 
    return 0;
}