【dfs】买门票

买门票

题目大意：

给出一些字母，求出可组合成的组合（要按顺序，和一定的规则）

原题：

题目描述

mxy 正要经过新世界的大门。
现在有很多人在门口排队，每个人将会被发到一个有效的通行密码作为门票。一个有
效的密码由 L(3 <= L <= 15)个小写字母(‘a’…‘z’)组成，至少有一个元音(‘a’, ‘e’, ‘i’,
‘o’ 或 ‘u’)和两个辅音(除去元音以外的音节)，并且是按字母表顺序出现的(例如，‘abc’
是有效的，而’bac’不是) 。
mxy 想要知道今天的有效密码是什么。
现在给定一个期望长度 L 和 C（1 <= C <= 26）个小写字母，写一个程序，输出所有的
长度为 L、能由这给定的 C 个字母组成的有效密码。密码必须按字母表顺序打印出来，一行
一个。

输入

输入数据共 2 行。
第 1 行: 两个由空格分开的整数，L 和 C。（3 <= L <= 15，1 <= C <= 26）
第 2 行: C 个由 1 个空格隔开的小写字母，密码是由这个字母集中的字母来构建的。

输出

若干行，每行输出一个长度为 L 个字符的密码(没有空格)。输出行必须按照字母顺序
排列。你的程序只需输出前 25000 个有效密码，即使后面还存在有效密码。

输入样例

4 6
a t c i s w

输出样例

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

解题思路：

直接dfs枚举每个位置就可以了

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int l,c,sum;
char d[105],a[105];
char read()
{
	char x;
	cin>>x;
	while (x<'a'||x>'z') cin>>x;//避开其他的
	return x;
}
void dfs(int dep,int y,int k)
{
	if (sum>=25000) return;
	if (dep>l)
	  {
	  	if (y>=1&&l-y>=2)//符合规则
	  	  {
	  	  	sum++;
	  	  	for (int i=1;i<=l;++i)
	  	  	  putchar(d[i]);
	  	  	putchar(10);
	  	  }
	  	return;
	  }
	for(int i=k;i<=c;++i)
	  {
	  	d[dep]=a[i];//记录
	  	if (a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u')//元音字母
	  	  dfs(dep+1,y+1,i+1);//dfs
	  	else dfs(dep+1,y,i+1);
	  }
}
int main()
{
	scanf("%d %d",&l,&c);
	for (int i=1;i<=c;++i)
	  a[i]=read();
	sort(a+1,a+1+c);//排序
	dfs(1,0,1);
}