【错题集-编程题】四个选项（DFS + 剪枝 + 哈希表）

牛客对应题目链接：四个选项 (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 这类题目主要就是考察代码编写能力，后期可以多做类似的题目