Prime Path(bfs)

题意：给两个四位数n,m,将n变成m需要多少步，要求每次只能改变n的某一位数，即改变后的数与改变前的数只有一位不同，且每次改变后的数都是素数。

思路：bfs+枚举每一位+素数筛选。

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <string.h>
 4 using namespace std;
 5 const int N=10000;
 6 int prime[N],vis[N],b[4];
 7 void is_prime()
 8 {
 9     memset(prime,0,sizeof(prime));
10     for (int i = 3; i <= 10000; i ++)
11     {
12         prime[i] = i%2;
13     }
14     for (int i = 0; i <= 100; i ++)
15     {
16         if (prime[i])
17         {
18             for (int j = 2*i; j <= 10000; j += i)
19             {
20                 prime[j] = 0;
21             }
22         }
23     }
24     memset(prime,0,1000*sizeof(int));//只保留1000至9999以内的素数
25 }
26 int bfs(int l,int r)
27 {
28     int step[N],num ;
29     memset(vis,0,sizeof(vis));
30     memset(step,0,sizeof(step));
31     queue<int>q;
32     q.push(l);
33     vis[l] = 1;
34     while(!q.empty())
35     {
36         int ll = q.front();
37         q.pop();
38         b[0] = ll%10;//个
39         b[1] = ll/10%10;//十
40         b[2] = ll/100%10;//百
41         b[3] = ll/1000;//千
42         for (int i = 0; i < 4; i ++)
43         {
44             int t = b[i];//将该位上的数保存，便于恢复
45             for (int j = 0; j < 10; j ++)//枚举
46             {
47                 if(t!=j)
48                 {
49 
50                     b[i] = j;
51                     num = b[3]*1000+b[2]*100+b[1]*10+b[0];
52                     if (!vis[num] && prime[num])//是素数并且没有枚举过
53                     {
54                         q.push(num);
55                         vis[num] =1;
56                         step[num] = step[ll]+1;//当前步数为上一状态的步数加1。
57                     }
58                     if (num==r)
59                     {
60                         return step[num];
61                     }
62                 }
63 
64             }
65             b[i] = t;//恢复该位上的数
66         }
67     }
68     return -1;
69 }
70 int main()
71 {
72     int t,n,m;
73     is_prime();
74     scanf("%d",&t);
75     while(t--)
76     {
77         scanf("%d%d",&n,&m);
78         int ans = bfs(n,m);
79         if (ans==-1)
80             printf("Impossible
");
81         else
82             printf("%d
",ans);
83 
84     }
85     return 0;
86 }

View Code