【题解】NC202493 四个选项（DFS + 剪枝 + 哈希表）

https://ac.nowcoder.com/acm/problem/202493

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 每个选项最多出现的次数，初始化为0，数组大小为5，索引1-4对应A-D，索引0未使用
vector<int> counts(5, 0); 
// 一个二维数组，用于记录题目之间是否答案必须相同，初始化为false
bool same[13][13] = {false}; 
// 记录当前选择的答案序列，初始化为包含第一个索引未使用
vector<int> path(1, 0);
// 用于统计所有可能的方案数
long long ret;

// 判断当前位置pos是否可以放置选项cur
bool isSame(int pos, int cur) {
    for (int i = 1; i < pos; ++i) {
        // 如果之前有题目和当前题目答案必须相同，且当前答案与之前不同，则返回false
        if (same[pos][i] && path[i] != cur) return false;
    }
    // 如果所有检查都通过，则返回true
    return true;
}

// 深度优先搜索函数，用于找出所有可能的方案
void dfs(int pos) {
    if (pos > 12) {
        // 如果已经处理完所有题目，则增加方案数并返回
        ++ret;
        return;
    }
    
    // 遍历所有选项A-D
    for (int i = 1; i <= 4; ++i) {
		// 剪枝
        // 如果当前选项的使用次数已经为0，则跳过
        if (counts[i] == 0) continue; 
        // 如果当前位置不能放置选项i，则跳过
        if (!isSame(pos, i)) continue; 
        
        // 选择当前选项i，减少其使用次数，并将其添加到答案序列中
        counts[i]--;
        path.push_back(i);
        // 递归处理下一道题目
        dfs(pos+1);
        // 回溯，将选项i从答案序列中移除，并增加其使用次数
        path.pop_back();
        counts[i]++;
    }
}

int main() {
    // 读取每个选项A-D出现的次数
    for (int i = 1; i <= 4; ++i) {
        cin >> counts[i];
    }
    // 读取额外条件的数量
    int m;
    cin >> m;
    // 读取额外条件，设置题目之间答案必须相同的关系
    while (m--) {
        int x, y;
        cin >> x >> y;
        same[x][y] = same[y][x] = true;
    }
    
    // 从第一题开始深度优先搜索
    dfs(1);
    // 输出所有可能的方案数
    cout << ret << endl;
    
    return 0;
}