牛客对应题目链接：四个选项 (nowcoder.com)
一、分析题目
用递归枚举出所有的情况，注意剪枝：
- 填写某个数时，要看看还有没有剩余次数。
- 填写某个数时，要看看符不符合若干题的选项必须相同。
二、代码
// 值得学习的代码
#include <iostream>
#include <vector>using namespace std;int cnt[5]; // ⽤数组存每⼀个选项出现多少次
int m, x, y;
bool same[13][13]; // 存哪些题的答案是相同的int ret;
vector<int> path; // 记录路径⾥⾯选了哪些选项bool isSame(int pos, int cur)
{for(int i = 1; i < pos; i++){if(same[pos][i] && path[i] != cur) return false;}return true;
}void dfs(int pos)
{if(pos > 12){ret++;return;}for(int i = 1; i <= 4; i++){if(cnt[i] == 0) continue; // 没有使⽤次数if(!isSame(pos, i)) continue; // 需要相同的位置，没有相同cnt[i]--;path.push_back(i);dfs(pos + 1);path.pop_back();cnt[i]++;}
}int main()
{for(int i = 1; i <= 4; i++) cin >> cnt[i]; cin >> m;while(m--){cin >> x >> y;same[x][y] = same[y][x] = true;}path.push_back(0); // 先放进去⼀个占位符dfs(1);cout << ret << endl;return 0;
}三、反思与改进
有一个剪枝的逻辑没弄明白，x 题和 y 题答案相同可以有一种剪枝策略，其中包含两个不同思路。dfs 这类题目主要就是考察代码编写能力，后期可以多做类似的题目