给出一个整数n（n≤2000）和k个变换规则（k≤15）。规则：
① 1个数字可以变换成另1个数字；
② 规则中，右边的数字不能为零。
例如：n=234，k=2规则为
2 → 5
3 → 6
上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数。
求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。
输入
第一行为n，第二行为k。
后面有k行，每行两个数xi和yi，表示n中的数组xi可以变换成yi。
输出
格式为一个整数（满足条件的整数个数）。
样例输入
样例输出
解题思路 求一个数可以有几种情况到它 可以dfs也可以bfs+映射当然也可以floyd
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <map> 5 #include <set> 6 #include <queue> 7 using namespace std; 8 string name; 9 int k,len; 10 int res[2005]; 11 int arr[35]; 12 int vis[11]; 13 int ma[11]; 14 int a[20],b[20]; 15 16 void calculation(int x){ 17 int jw=0; 18 for(int i=0;i<=len;i++){ 19 int temp=arr[i]*x+jw; 20 arr[i]=temp%10; 21 jw=temp/10; 22 } 23 while(jw){ 24 arr[++len]=jw%10; 25 jw/=10; 26 } 27 } 28 29 int ans; 30 void dfs(int n){ 31 vis[n]=1; 32 ans++; 33 for(int i=1;i<=k;i++){ 34 if(a[i]==n&&vis[b[i]]==0){ 35 dfs(b[i]); 36 } 37 } 38 } 39 40 int main(){ 41 ios::sync_with_stdio(false); 42 cin>>name; 43 cin>>k; 44 for(int i=0;i<=9;i++) ma[i]=-1; 45 for(int i=1,d1,d2;i<=k;i++){ 46 cin>>a[i]>>b[i]; 47 48 } 49 arr[0]=1; 50 for(int i=0;i<name.size();i++){ 51 ans=0; 52 memset(vis,0,sizeof(vis)); 53 dfs(name[i]-‘0‘); 54 calculation(ans); 55 } 56 for(int i=len;i>=0;i--) cout << arr[i]; 57 cout << endl; 58 return 0; 59 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <map> 5 #include <set> 6 #include <queue> 7 using namespace std; 8 string name; 9 int k,len; 10 int res[2005]; 11 int arr[35]; 12 multimap<int,int> ma; 13 14 int bfs(int n){ 15 set<int> se; //能变换的数字 16 se.insert(n); 17 queue<int> que; 18 que.push(n); 19 while(!que.empty()){ 20 int u=que.front(); 21 que.pop(); 22 for(multimap<int,int>::iterator it=ma.begin();it!=ma.end();it++){ 23 if(u==it->first&&!se.count(it->second)){ 24 se.insert(it->second); 25 que.push(it->second); 26 } 27 } 28 } 29 return se.size(); 30 } 31 32 void calculation(int x){ 33 int jw=0; 34 for(int i=0;i<=len;i++){ 35 int temp=arr[i]*x+jw; 36 arr[i]=temp%10; 37 jw=temp/10; 38 } 39 while(jw){ 40 arr[++len]=jw%10; 41 jw/=10; 42 } 43 } 44 45 46 int main(){ 47 ios::sync_with_stdio(false); 48 cin>>name; 49 cin>>k; 50 for(int i=1,d1,d2;i<=k;i++){ 51 cin>>d1>>d2; 52 ma.insert(make_pair(d1,d2)); 53 } 54 for(int i=0;i<name.size();i++){ 55 res[i]=bfs(name[i]-‘0‘); 56 } 57 // for(int i=0;i<name.size();i++){ 58 // cout << res[i] << endl; 59 // } 60 arr[0]=1; 61 for(int i=0;i<name.size();i++){ 62 calculation(res[i]); 63 } 64 for(int i=len;i>=0;--i){ 65 cout << arr[i]; 66 } 67 cout << endl; 68 return 0; 69 }
原文：https://www.cnblogs.com/qq-1585047819/p/11255619.html
