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);
}