PKU 3049-Securing the Barn
問題概要
L文字のパスワードをC種類の英小文字を用いて以下の規則にそって作成する
・同じ文字は二度と使えない
・必ず母音が1音以上含まれる
・必ず子音が2音以上含まれる
・文字が辞書順である
解法
DFSする
実装(C)
#include <stdio.h> #include <stdlib.h> int L,C; char c[26]; char s[2]; char res[15]; void solve(int x,int nowl,int nowa){ if(nowl==L){ if(nowa>=1&&nowl-nowa>=2){ printf("%s\n",res); } return; } if(x==26)return; //この文字を使う if(c[x]){ if(x+'a'=='a'||x+'a'=='u'||x+'a'=='i'||x+'a'=='e'||x+'a'=='o'){ res[nowl]=x+'a'; solve(x+1,nowl+1,nowa+1); }else{ res[nowl]=x+'a'; solve(x+1,nowl+1,nowa); } } //この文字を使わない solve(x+1,nowl,nowa); } int main() { int i; scanf("%d%d",&L,&C); for(i=0;i<C;i++){ scanf("%s",s); c[s[0]-'a']=1; } solve(0,0,0); }