题目描述
给出一个整数 n 和 k 个变换规则。
规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：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
（n< 10^30)
（k< =15）
输出格式
一个整数（满足条件的个数）
样例输入
234 2 2 5 3 6
样例输出
4
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
int cnt, len;
int head[10];
bool visited[10];
int transform[10]; //存储1-9每个数能变的可能数
int a[250];
void HighAccuracyMutiplication(int a[], int n) //高精度乘法
{
len = a[0];
char tmp[100];
sprintf(tmp, "%d", n);
for (int i = 1; i <= len; i++)
a[i] *= n;
for (int i = 1; i <= len; i++) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
len = a[0] + strlen(tmp); //因为两数之积的位数不超过两数位数之和
while (a[len] == 0 && len > 1) len--;
a[0] = len;
}
struct Edge { //链式前向星储存数的变换法则，用邻接矩阵/邻接表也行
int next, to;
};
struct Edge edge[15];
typedef struct QNode { //萌新没学过c++QAQ，每次做图的题都要自己实现队列
int Data[20];
int front, rear;
}*Queue;
void Enqueue(int item, Queue Q) //入队
{
Q->rear = (Q->rear + 1) % 20;
Q->Data[Q->rear] = item;
}
int Dequeue(Queue Q) //出队
{
Q->front = (Q->front + 1) % 20;
return Q->Data[Q->front];
}
void add(int u, int v) //链式前向星的加边操作
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int BFS(int element, Queue Q) //查找指定数字所有可能变换结果，也就是图里与该数连通的数字
{
memset(visited, 0, sizeof(visited));
visited[element] = true;
Enqueue(element, Q);
int V, sum = 1;
while (Q->front != Q->rear) {
V = Dequeue(Q);
for (int i = head[V]; i != -1; i = edge[i].next) {
if (!visited[edge[i].to]) {
sum++;
Enqueue(edge[i].to, Q);
visited[edge[i].to] = true;
}
}
}
return sum;
}
int main()
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->front = Q->rear = 0;
memset(head, -1, sizeof(head));
int k, u, v;
char s[32];
scanf("%s", s);
scanf("%d", &k);
while (k--) {
scanf("%d%d", &u, &v);
add(u, v);
}
for (int i = 0; i <= 9; i++)
transform[i] = BFS(i, Q);
a[0] = a[1] = 1;
for (int i = 0; i < strlen(s); i++)
HighAccuracyMutiplication(a, transform[s[i] - '0']);
for (int i = len; i >= 1; i--) printf("%d", a[i]);
return 0;
}