PKU : 3049 - Securing the Barn

問題概要

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

M個のアルファベットを使って, 次の条件を満たすN文字の文字列を作ってください.

• 母音の文字を最低1回使う
• 子音の文字を最低2回使う
• 文字列の先頭から末尾まで, アルファベット順に並ぶ

複数の文字列が作れる場合は, 辞書式順で出力すること.

アルゴリズム

深さ優先探索で解けます.
M個の文字はソートして, 先頭から順番に使いましょう.

プログラム

int n,m;
char t[128];

void dfs(int rem,int idx,int vowel,int con,string s){
  if(rem == 0){
    if(vowel >= 1 && con >= 2) cout<<s<<endl;
    return;
  }

  for(int i=idx;i<m;i++){
    bool flg = (t[i] == 'a' || t[i] == 'i' || t[i] == 'u' || t[i] == 'e' || t[i] == 'o');
    dfs(rem-1,i+1,vowel+flg,con+!flg,s+t[i]);
  }
}

int main(void){
  cin>>n>>m;
  rep(i,m) cin>>t[i];
  sort(t,t+m);
  dfs(n,0,0,0,"");
}