1122-What is the Number in my Mind ?

問題概要

L個のそれぞれ異なる数字(0〜9)を用いた数に対してヒットアンドブローを行う。
h個の数に対するヒット数とブロー数が与えられるので、元の数が一意に復元できるかを調べろ。
一意に求められる場合はその数を求めよ。

考え方

DFSで数字を確定させていく。
このとき、ヒット数とブロー数と外れた数はそれぞれ増えるだけなので、
入力のヒット数、ブロー数、外れた数を越えたものを枝刈りする。
/*時間制限がなかったらnext_permutation安定だと思う*/

実装(C++)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;

struct data{
    int blow,hit;
    vector<int> val;
    vector<int> has;
};

istream &operator>>(istream &is,data &a){
    string t;
    is>>t>>a.hit>>a.blow;
    a.val=vector<int>(t.size());
    a.has=vector<int>(10);
    for(int i=0;i<t.size();i++){
	a.val[i]=t[i]-'0';
	a.has[t[i]-'0']=1;
    }
    return is;
}
ostream &operator<<(ostream &os,vector<int> &v){
    for(int i=0;i<v.size();i++){
	os<<v[i];
    }  
    return os;
}

int L,h;
vector<int> val;
vector<int> ans;
int res;
vector<data> datas;
bool used[10];

inline bool check(int x){
    for(int i=0;i<h;i++){
	int blow=0,hit=0;
	for(int j=0;j<x;j++){
	    if(datas[i].val[j]==val[j])hit++;
	    blow+=datas[i].has[val[j]];
	}
	
	if(datas[i].hit<hit)return false;
	if(datas[i].blow<blow-hit)return false;
	if(L-datas[i].hit-datas[i].blow<x-blow)return false;
    }
    return true;
}

void solve(int x){
    if(!check(x))return;
  
    if(x==L){
	ans=val;res++;
	return;
    }
 
  for(int i=0;i<10;i++){
    if(used[i]==false){
	used[i]=true;
	val[x]=i;
	solve(x+1);
	if(res>1)return;
	used[i]=false;	
    }
  }
}

int main(){
    for(;cin>>L>>h;){
	if(L==0&&h==0)break;
	val=vector<int>(L);
	datas=vector<data>(h);
	
	for(int i=0;i<h;i++){
	    cin>>datas[i];
	}
	res=0;
	memset(used,0,sizeof(used));
	solve(0);
	if(res==1){
	    cout<<ans<<endl;
	}else{
	    cout<<"NO"<<endl;
	}
    }
}