题目描述
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－>5
3－>6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234 534 264 564 共 4 种不同的产生数
问题：
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入输出格式
输入格式： 键盘输人，格式为：
n k x1 y1 x2 y2 … …
xn yn
输出格式： 屏幕输出，格式为：
一个整数（满足条件的个数）：
输入输出样例
输入样例#1： 234 2 2 5 3 6 输出样例#1： 4
https://www.luogu.org/PRoblem/show?pid=1037
一个数字能变换的种类为可直接变换的和可间接变换的 比如 1 2 2 3
那么就自动多出来一个条件 1 3
就是1 有三种变化
这种情况用弗洛伊德算法 找到一个数字可以变化的次数和 之后在连续乘起来 得到的结果就是变化次数
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <queue>#include <cmath>#include <stdlib.h>using namespace std;int tag[10][10];int d[10];int p[1000];int main(){ string a; int n; while(cin>>a>>n) { int x,y; for(int i=0;i<n;i++) { cin>>x>>y; tag[x][y]=1; } for(int k=1;k<=9;k++) for(int i=0;i<=9;i++) for(int j=1;j<=9;j++) if(tag[i][k]&&tag[k][j]) tag[i][j]=1;//可以间接转化的数，并且注意这个i,j,k的排列。只有这种排列可以找到所有情况 for(int i=0;i<10;i++) { tag[i][i]=1; for(int j=0;j<10;j++) if(tag[i][j]) d[i]++; } int z=0; p[0]=1; for(int i=0;a[i];i++) { z=0; int x=d[a[i]-'0']; //cout<<x<<endl; for(int i=0;i<500;i++) { p[i]=(p[i]*x+z); z=p[i]/10; p[i]%=10; //cout<<p[i]; } //cout<<endl; } int i=500; while(p[i]==0) i--; for(;i>=0;i--) { cout<<p[i]; } cout<<endl; }}弗洛伊德算法在用直接关系找间接关系的话比较方便
新闻热点
疑难解答
