【题解-信息学奥赛一本通】1361：产生数(Produce)
)
题目：1361：产生数(Produce)
题目描述
给出一个整数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，表示一条规则为 xi→yi。
输出
格式为一个整数（满足条件的整数个数）。
时空限制
1s / 64MB
样例输入
234 2 2 5 3 6样例输出
4代码
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=20000+10;intn,k,x,y,ans;vector<int>a;PII g[N];boolvis[N];voidsplitnum(intnum){a.clear();while(num>0){a.push_back(num%10);num/=10;}reverse(a.begin(),a.end());}inttrans(intt,inty){intsum=0;for(inti=0;i<a.size();i++){if(i!=t)sum=sum*10+a[i];elsesum=sum*10+y;}returnsum;}voidbfs(intm){queue<int>q;q.push(m);vis[m]=true;ans=1;while(!q.empty()){intt=q.front();q.pop();splitnum(t);for(inti=0;i<a.size();i++)for(intj=0;j<k;j++)if(a[i]==g[j].first){inttt=trans(i,g[j].second);if(!vis[tt]){q.push(tt);vis[tt]=true;ans++;}}}}intmain(){cin>>n>>k;for(inti=0;i<k;i++){cin>>x>>y;g[i].first=x,g[i].second=y;}bfs(n);cout<<ans;return0;}