2002年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。 规则: 一位数可变换成另一个一位数: 规则的右部不能为零。 例如:n=234。有规则(k=2): 2-> 5 3-> 6 上面的整数 234 经过变换后可能产生出的整数为(包括原数): 234 534 264 564 共 4 种不同的产生数 问题: 给出一个整数 n 和 k 个规则。 求出: 经过任意次的变换(0次或多次),能产生出多少个不同整数。 仅要求输出个数。
输入描述 Input Description
键盘输人,格式为: n k x1 y1 x2 y2 ... ... xn yn
输出描述 Output Description
屏幕输出,格式为: 一个整数(满足条件的个数)
样例输入 Sample Input
234 2 2 5 3 6
1 #include<iostream>
2 using namespace std;
3 int can[1001][1001];
4 long long int tot=1;
5 int main()
6 {
7 string n;
8 int m;
9 cin>>n;
10 cin>>m;
11 for(int i=1;i<=m;i++)
12 {
13 int x,y;
14 cin>>x>>y;
15 can[x][y]=1;
16 can[y][x]=1;
17 }
18 for(int i=0;i<10;i++)
19 {
20 for(int j=0;j<10;j++)
21 {
22 for(int k=0;k<10;k++)
23 {
24 if(j!=i&&i!=k&&j!=k)
25 {
26 if(can[i][j]==1&&can[i][k]==1)//将所有可能的情况计算出来 2->3 3->5 2->5
27 can[k][j]=1;
28 }
29 }
30 }
31 }
32 for(int i=0;i<n.length();i++)
33 {
34 int d=n[i]-48;
35 int now=1;
36 for(int j=0;j<10;j++)
37 {
38 if(can[d][j]==1&&d!=j)
39 {
40 now++;
41 }
42 }
43 tot=tot*now;// 乘法原理
44 }
45 cout<<tot;
46 return 0;
47 }