↓ 跳过正文
题解：UVA628 Passwords

题解：UVA628 Passwords

xyx404
作者
xyx404
Have a nice day.
目录

封面

题意：
#

有多组数据。

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

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

思路：
#

深度优先搜索。

深度优先搜索函数传入两个量 $now$ 和 $ans$。

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

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

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