PKU : 3340 - Barbara Bennett's Wild Numbers

問題概要

http://poj.org/problem?id=3340

自然数Aと自然数Bが入力されます.
ただし, 自然数Aのどこかのケタは, '?'で隠されている可能性があります.
このとき, Bより大きくなるようなAは, いくつ作れるでしょう.

アルゴリズム

あるケタより上が等しいか等しくないかで分岐して, DFSしました.
もっと簡単な書き方があるかもしれないです.

プログラム

ll ans;
int n;
string a,b;

void dfs(int idx,bool eq,ll mul){
  if(idx == n){
    if(!eq) ans += mul;
    return;
  }

  if(eq){
    if(a[idx] == '?'){
      if(b[idx] != '9') dfs(idx+1,false,mul*(ll)('9'-b[idx]));
      dfs(idx+1,true,mul);
    }
    else{
      if(a[idx] < b[idx]) return;
      if(a[idx] == b[idx]) dfs(idx+1,true,mul);
      else dfs(idx+1,false,mul);
    }
  }
  else{
    if(a[idx] != '?'){
      dfs(idx+1,false,mul);
    }
    else{
      dfs(idx+1,false,mul*10LL);
    }
  }
}

int main(void){
  while(cin>>a,a!="#"){
    cin>>b;
    n = a.length();
    ans = 0;
    dfs(0,true,1);
    cout<<ans<<endl;
  }
}