首页 > 代码库 > POJ 3126 BFS
POJ 3126 BFS
题意
将一个四位的素数,变为另一个四位的素数。每次只能换一位上的数字,不能存在前导0,且中间过程中,换掉一位数字后的数也都是素数。
问最少变换的次数
分析
bfs即可
代码
1 /* When all else is lost the future still remains. */
2 /* You can be the greatest */
3 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++)
4 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--)
5 #define fi first
6 #define se second
7 #define mk(X,Y) make_pair((X),(Y))
8 #define inf 0x3f3f3f3f
9 #define clr(X,Y) memset(X,Y,sizeof(X))
10 #define pb push_back
11 //head
12 #include <iostream>
13 #include <stdio.h>
14 #include <queue>
15 #include <algorithm>
16 #include <string>
17 #include <map>
18 #include <string.h>
19 using namespace std;
20 bool primer[10010];
21 int val[10010];
22 bool cur[10010];
23 bool is(int in){
24 for(int i = 2 ; i * i <= in ; i++)
25 if(in % i == 0) return 0;
26 return 1;
27 }
28 void init(){
29 clr(primer,0);
30 rep(i,1000,10000) if(is(i)) primer[i] = 1;
31 return ;
32 }
33 int num(int in[5]){
34 return in[0]*1000+in[1]*100+in[2]*10+in[3];
35 }
36 void slove(int be , int end){
37 clr(val,0);
38 clr(cur,0);
39 //
40 queue<int> Q;
41 Q.push(be);
42 //
43 while(!Q.empty()){
44 if(cur[end]) break;
45 int now = Q.front();
46 cur[now] = 1;
47 int t = now;
48 Q.pop();
49 int p[5];
50 drep(i,3,0){
51 p[i] = t % 10;
52 t /= 10;
53 }
54 rep(i,0,4){
55 int a = p[i];
56 rep(j,0,10){
57 if(!i && !j) continue;
58 if(a == j) continue;
59 p[i] = j;
60 int k = num(p);
61 if(!primer[k]) continue;
62 if(cur[k]) continue;
63 val[k] = val[now] + 1;
64 cur[k] = 1;
65 Q.push(k);
66 }
67 p[i] = a;
68 }
69 }
70 return;
71 }
72 int main(){
73 init();
74 int n;
75 while(~scanf("%d",&n)) while(n--){
76 char s1[5],s2[5];
77 int pre[5],after[5];
78 scanf("%s %s",s1,s2);
79 //
80 rep(i,0,4){
81 pre[i] = s1[i] - ‘0‘;
82 after[i] = s2[i] - ‘0‘;
83 }
84 //printf("%d %d\n",num(pre),num(after));
85 slove(num(pre),num(after));
86 //
87 if(!cur[num(after)]) printf("Impossible\n");
88 else printf("%d\n",val[num(after)]);
89 }
90 return 0;
91 }
POJ 3126 BFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。