UVa296 Safebreaker

問題
http://uva.onlinejudge.org/external/2/296.html

概要
0000 〜 9999 までの4桁の数字列に Hit And Blow をする。質問とそのときのHit数とBlow数が与えられるので、4桁の数字が一意に特定できるならば、その値を出力せよ。また複数候補がある場合は "indeterminate" と出力し、解が定まらない場合は "impossible" と出力せよ。

解法
解の候補となる4桁の数字列を for(int i=0; i<10000; i++) {...} で決め打ちし、質問をすべて満たすかどうかチェックする。
質問を満たさないための条件のポイントは以下

• 一度Hitした位置の数字は、解の候補と質問ともにBlowにカウントしない
• 一度Blowした位置の数字は、解の候補と質問それぞれで二度以上Blowにカウントしない
• など（要復習）

「など」と書いたのは cand[i] = 'B'（Hitの記録とは異なる文字）とすると何故ACかがよく分かってないから。はじめに書いたときは意味が分かってて分けたつもりだったけれど、今はどうしてかよくわからなくなってる。

#include <bits/stdc++.h>

using namespace std;
 
#define rep(i,n) for(int i=0; i<(n);i++)
 
int G;
string input[10];
int hit[10], blow[10];
 
string toHBStr(int x) {
  string ret;
    
  ret += static_cast<char>('0' + x/1000);
  ret += static_cast<char>('0' + x/100%10);
  ret += static_cast<char>('0' + x/10%10);
  ret += static_cast<char>('0' + x%10);
    
  return ret;
}
 
bool isValidHit(string &cand, int idx) {
   
  int hit_cnt = 0;
   
  rep(i, 4) {
    if(cand[i] == input[idx][i]) {
      hit_cnt ++;
      cand[i] = 'H';
    }
  }
   
  if(hit_cnt != hit[idx]) return false;
  return true;
}
 
bool isValidBlow(string &cand, int idx) {
   
  int blow_cnt = 0;
  bool input_used[4] = {};
  rep(i, 4) {
    if(cand[i] == 'H') continue;
    rep(j, 4) {
      if(cand[j] == 'H') continue;
      if(input_used[j]) continue;
      
      if(cand[i] == input[idx][j]) {
        blow_cnt ++;
        cand[i] = 'B';
        input_used[j] = 1;
      }
      
    }
  }
   
  if(blow_cnt != blow[idx]) return false;
  return true;
}
 
bool isValid(int x) {
   
  bool ok = 1;
  rep(i, G) {
    string cand = toHBStr(x);
    if(!isValidHit(cand, i)) { ok = 0; break; }
    if(!isValidBlow(cand, i)) { ok = 0; break; }
  }
   
  return ok;
}
 
int main() {
    
  int Tc; cin >> Tc;
    
  while(Tc--) {
    cin >> G;
    for(int i=0; i<G; i++) {
      cin >> input[i];
      scanf("%d/%d", &hit[i], &blow[i]);
    }
     
    enum { OK, MULTI, IMP };
    int judge = IMP;
    int ans;
     
    for(int i=0; i<10000; i++) {
      if(isValid(i)) {
        if(judge == OK) {
          judge = MULTI;
          break;
        }
        else {
          judge = OK;
          ans = i;
        }
      }
    }
      
    if(judge == OK) {
      cout << toHBStr(ans) << endl;
    }
    if(judge == MULTI) {
      cout << "indeterminate" << endl;
    }
    if(judge == IMP) {
      cout << "impossible" << endl;
    }
      
  }
    
  return 0;
}