题目大意&＃xff1a;给定两个四位素数a b&＃xff0c;要求把a变换到b&＃xff0c;变换的过程要保证 每次变换出来的数都是一个 四位素数&＃xff0c;而且当前这步的变换所得的素数 与 前一步得到的素数 只能有一个位不同&＃xff0c;而且每步得到的素数都不能重复。
题目链接&＃xff1a;点击打开链接
分析&＃xff1a;分析可知这题肯定是用搜索&＃xff0c;每次改变某位&＃xff0c;每位有0-9&＃xff08;首位无0&＃xff09;10种变法&＃xff0c;一共40个方向&＃xff0c;可是到底DFS还是BFS还是二分呢&＃xff1f;只二分对这题显然是不太好写的&＃xff0c;DFS的话复杂度为O&＃xff08;40^n&＃xff09;估计几年也出不了结果来&＃xff0c;&＃xff0c;&＃xff0c;然后BFS的话O&＃xff08;40*n&＃xff09;肯定是可以过的。BFS是很好写&＃xff0c;麻烦的就在数字的转变和素数的判断。这里素数的判断由于是多组数据我们可以用埃式筛选打一个表&＃xff08;怎么实现可以直接看代码&＃xff0c;自己思考下就行了&＃xff0c;这里朴素的方法也是可以过的&＃xff09;。对于改变一个数字的某一位我们可以用到sprintf和sscanf这2个黑科技来简单的实现&＃xff0c;只要先把初始数字用sprintf打印到字符串里&＃xff0c;然后利用字符串的随机访问来改变其中某一位就行了&＃xff0c;接下来再用sscanf再输出到temp1中即可。
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 #define N 100005
7
8 bool prime[N],mark[N];
9 int in,out;
10
11 void bfs()
12 {
13 int i,j;
14 queue<int> q;
15 queue<int> a;//存步数
16
17 memset(mark,0,sizeof(mark));
18 q.push(in);
19 a.push(0);
20 mark[in]&＃61;1;
21 while (!q.empty())
22 {
23 int temp&＃61;q.front();
24 int ta&＃61;a.front();
25 q.pop();
26 a.pop();
27 if (temp&＃61;&＃61;out)
28 {
29 printf("%d\n",ta);
30 return;//出口记得return!!!
31 }
32 for (i&＃61;0;i<4;i&＃43;&＃43;)
33 {
34 for (j&＃61;0;j<&＃61;9;j&＃43;&＃43;)
35 {
36 if (0&＃61;&＃61;i&&0&＃61;&＃61;j)//是千位不能为0,所以是0&＃61;&＃61;i&&0&＃61;&＃61;j!!!
37 {
38 continue;
39 }
40 char s[6]&＃61;"\0";
41 sprintf(s,"%d",temp);
42 s[i]&＃61;j&＃43;&＃39;0&＃39;;
43 int temp1;
44 sscanf(s,"%d",&temp1);//新数要新的变量存储&＃xff0c;不能用temp!!!
45 if (prime[temp1]&&!mark[temp1])
46 {
47 q.push(temp1);
48 mark[temp1]&＃61;1;
49 a.push(ta&＃43;1);
50 }
51 }
52 }
53 }
54 printf("Impossible\n");
55 }
56
57 void cprime()//打素数表
58 {
59 int i,j;
60 memset(prime,true,sizeof(prime));
61 prime[0]&＃61;prime[1]&＃61;false;
62 for (i&＃61;2;i
63 {
64 if (prime[i])
65 for (j&＃61;2*i;j
66 {
67 prime[j]&＃61;false;
68 }
69 }
70 }
71
72 int main()
73 {
74 int t;
75
76 cprime();
77 scanf("%d",&t);
78 while (t--)
79 {
80 scanf("%d %d",&in,&out);
81 bfs();
82 }
83
84 return 0;
85 }
京公网安备 11010802041100号