题解：UVA628 Passwords

封面

题意：

有多组数据。

给出 nn 个字符串和 kk 个规则，求每个规则可以组成的所有密码。

在规则中 # 表示的是一个给出的字符串，0 表示的是 00 到 99 中的一个数字。

思路：

深度优先搜索。

深度优先搜索函数传入两个量 nownow 和 ansans。

其中 nownow 表示的是现在是规则里下标为 now+1now+1 字符，ansans 表示现在搜索到的答案。

当规则里下标为 now+1now+1 字符为 # 时，遍历给出的字符串，对于每一个给出的字符串都放在 ansans 后进行一次 dfs，注意不能影响后面的操作，如当遍历的是第 ii 个给出的字符串时，不能影响第 i+1i+1 及其之后的操作。
当规则里下标为 now+1now+1 字符为 0 时，把 00 到 99 按顺序放一次，同样不能影响后面的操作。
具体的代码为：

if(r[now]=='#'){// 是一个给出的字符串 
  for(int i=1;i<=n;i++){
    dfs(now+1,ans+s[i]);
  }
}
else if(r[now]=='0'){// 是一个数字
  for(int i=0;i<=9;i++){
    char a=i+'0';
    dfs(now+1,ans+a);
  }
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n,m;
string r;
string s[120];
void dfs(int now/*现在是 r 的第几个字符*/,string ans/*答案*/){
	if(now>=r.size()){
		cout<<ans<<"\n";
		return;
	} 
	if(r[now]=='#'){// 是一个给出的字符串 
		for(int i=1;i<=n;i++){
			dfs(now+1,ans+s[i]);
		}
	}
	else if(r[now]=='0'){
		for(int i=0;i<=9;i++){
			char a=i+'0';
			dfs(now+1,ans+a);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while(cin>>n){// 不确定组数，每次如果有 n 输入说明有一组 
		cout<<"--\n";
		for(int i=1;i<=n;i++)cin>>s[i];
		cin>>m;
		for(int i=1;i<=m;i++){
			cin>>r;
			dfs(0,"");
		} 
	}
	return 0;
}