【題解】ZeroJudge e718: 108北二2.數字猜謎

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e718

#include <iostream>
using namespace std;

int n, m, used[10], a[1000005], b[1000005], ans;
string s[1000005], guess;

bool check(string x, string y, int a, int b){
    int arr[10] = {}, cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++){
        arr[y[i]-'0'] = 1;
        if (x[i] == y[i]) cnt1++;
    }
    for (int i = 0; i < 10; i++){
        if (used[i] && arr[i]) cnt2++;
    }
    if (cnt1 == a && cnt2 == (a+b)) return true;
    return false;
}
void fill(int pos){
    if (pos == n){
        for (int i = 0; i < m; i++){
            if (!check(guess, s[i], a[i], b[i])) return;
        }
        ans++;
        return;
    }
    for (int i = 0; i < 10; i++){
        if (!used[i]){
            used[i] = 1;
            guess[pos] = (char)('0'+i);
            fill(pos+1);
            used[i] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> s[i] >> a[i] >> b[i];
    }
    for (int i = 0; i < n; i++){
        guess += " ";
    }
    fill(0);
    cout << ans << "\n";
}
分享本文 Share with friends