AOJ : 2084 - Hit and Blow

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2084
ヒット＆ブローというゲームがあります. ヒット＆ブローは次の問題で確認してください. ( http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0025&lang=jp )
AさんとBさんがいて, Aさんはある秘密の4ケタの数字を持っています.(この数字は, 各桁の数字が異なる4ケタの数) Bさんがある数字を発言すると, Aさんは, 自分が持っている秘密の数とBさんの数を見て, ヒット数とブロー数を返してくれます.

このようなルールのとき, ゲームのプレイ履歴が入力として与えられます. この履歴を見て, ゲーム終了後にBさんはAさんの秘密の数を1通りに確定させることができるかを答える問題です.
もし確定できるならば, その数を出力. できないとしても, さらにBさんがもう一回数字を発言することで, 1通りに確定させることができるならば, Bさんが発言する数字を出力. そのどちらでもないならば, ???? と出力.

アルゴリズム

全探索で解きましょう.
OBOGの解法が僕と全く同じだったので, そちらを参考にしてください.
Day2-A問題
( http://acm-icpc.aitea.net/index.php?2007%2FPractice%2F%B2%C6%B9%E7%BD%C9%2F%B9%D6%C9%BE )

プログラム

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

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

//ヒット数を返す
int hit(string a,string b){
  int res = 0;
  rep(i,4) if(a[i] == b[i]) res++;
  return res;
}

//ブロー数を返す
int blow(string a,string b){
  int res = 0;
  rep(i,4) rep(j,4){
    if(i == j) continue;
    if(a[i] == b[j]){
      res++;
      break;
    }
  }

  return res;
}

int main(void){
  vector<string> s,init;

  //4ケタの各桁が異なる数を列挙する
  rep(i,10) rep(j,10) rep(k,10) rep(l,10) {
    if(i != j && i != k && i != l && j != k && j != l && k != l){
      string str = "";
      str += '0' + i;
      str += '0' + j;
      str += '0' + k;
      str += '0' + l;
      init.push_back(str);
    }
  }

  int n;
  while(cin>>n,n){
    s = init;
    while(n--){
      string str;
      int h,b;
      cin>>str>>h>>b;

      vector<string> next;
      rep(i,s.size()){
        if(hit(str,s[i]) == h && blow(str,s[i]) == b){
          next.push_back(s[i]);
        }
      }
      s = next;
    }

    if(s.empty()){
      cout<<"????\n";
    }
    else if(s.size() == 1){
      cout<<s[0]<<endl;
    }
    else{
      bool ansFlg;
      rep(i,init.size()){
        bool used[5][5];
        memset(used,0,sizeof(used));
        ansFlg = true;

        rep(j,s.size()){
          int h = hit(init[i],s[j]);
          int b = blow(init[i],s[j]);
          if(used[h][b]){
            ansFlg = false;
            break;
          }
          used[h][b] = true;
        }

        if(ansFlg){
          cout<<init[i]<<endl;
          break;
        }
      }
      if(!ansFlg) cout<<"????\n";
    }
  }

  return 0;
}