【信息學奧賽一本通】第三部分_隊列 ex2_3produce 產生數，

【信息學奧賽一本通】第三部分_隊列 ex2_3produce 產生數，

　　給出一個整數n(n<=2000)(代碼可適用n<=10^31)和k個變換規則(k<=15)。

　　規則:1、1個數字可以變換成另1個數字；

　　　　 2、規則中右邊的數字不能為零。

　　BFS

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 1000
 4 
 5 char num[33];
 6 int len,q[maxn],Visited[11];
 7 long long ans = 1;
 8 
 9 int main (){
10 //    freopen ("produce.in","r",stdin);
11 //    freopen ("produce.out","w",stdout); 
12     
13     int i,j,k;
14     int K,x[16],y[16];
15     
16     scanf ("%s%d",num,&K);
17     for (i = 1;i<=K;i++)
18         scanf ("%d%d",x+i,y+i);
19     len = strlen (num);    
20         
21     int head = 0,tail = 0,temp;
22         
23     for (j = 0;j<len;j++){
24         temp = 1;
25         memset (Visited,0,sizeof(Visited));
26         q[++tail] = num[j]-'0';
27         do{
28             head++;
29             for (i = 1;i<=K;i++){
30                 if (q[head] == x[i] && Visited[y[i]] == 0){
31                     q[++tail] = y[i];
32                     temp++;            
33                     Visited[x[i]] = 1;
34                     Visited[y[i]] = 1;
35                 }
36                 
37             }
38         }while (head<tail);
39         ans*=temp;
40     }
41     
42     printf ("%lld",ans);
43     
44     return 0;
45 }