poj 3126 Prime Path (bfs)
http://poj.org/problem?id=3126
题意是说,给定两个四位素数a b 问从a变换到b,最少需要变换几次. 变换的要求是,每次只能改变一个数字,而且中间过程得到的四位数也必须为素数. 因为提到最少变换几次,容易想到bfs,bfs第一次搜到的一定是最短步数.
先打个素数表 然后写个函数判断两个四位数有几位数字不同,如果只有一位,返回true,否则返回false 然后竟然wa了两次! 下表写错! pri[k++]=i;是先给pri[k]赋值,再k++; pri[++k]=i;才是先增加,再赋值.这个搞错了.所以wa了....sad
1
2 /*************************************************************************
3 > File Name: code/poj/3126.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: Fri 24 Jul 2015 01:16:23 AM CST
7 ************************************************************************/
8
9 #include<iostream>
10 #include<iomanip>
11 #include<cstdio>
12 #include<algorithm>
13 #include<cmath>
14 #include<cstring>
15 #include<string>
16 #include<map>
17 #include<set>
18 #include<queue>
19 #include<vector>
20 #include<stack>
21 #define y0 abc111qqz
22 #define y1 hust111qqz
23 #define yn hez111qqz
24 #define j1 cute111qqz
25 #define tm crazy111qqz
26 #define lr dying111qqz
27 using namespace std;
28 #define REP(i, n) for (int i=0;i<int(n);++i)
29 typedef long long LL;
30 typedef unsigned long long ULL;
31 const int N =1E4+5;
32 int pri[N],which[N];
33 int a,b,k;
34 bool flag;
35 int d[N];
36 bool prime(int x)
37 {
38 for ( int i = 2 ; i*i<=x ;i++ )
39 {
40 if (x %i==0) return false;
41 }
42 return true;
43 }
44
45 bool ok (int x,int y)
46 {
47 if (d[y]!=-1) return false;
48 int res = 0; //记录两个数不对应不相等的数字的个数
49 int xx=x,yy=y;
50 while (x&&y)
51 {
52 if (x!=y) res++;
53 x = x/10;
54 y = y/10;
55 }
56 // if (res==1) cout<<"x:"<<xx<<" y:"<<yy<<endl;
57 if (res==1) return true;
58 return false;
59 }
60 void bfs()
61 {
62 queue<int>x;
63 memset(d,-1,sizeof(d));
64 x.push(a);
65 d[a]=0;
66 while (!x.empty())
67 {
68 int px = x.front();
69 // cout<<"px:"<<px<<endl;
70 x.pop();
71 if (px==b) return;
72 for ( int i = 0 ; i< k ; i++ )
73 {
74 if (ok(px,pri[i]))
75 {
76 d[pri[i]]=d[px]+1;
77 x.push(pri[i]);
78 }
79 }
80 }
81
82
83 }
84 int main()
85 {
86 k =0;
87 for ( int i = 1000; i <=9999; i++ )
88 {
89 if (prime(i))
90 {
91 pri[k++]=i;
92
93 }
94 }
95 int T;
96 // cout<<pri[0]<<endl;
97 // cout<<pri[1]<<endl;
98 cin>>T;
99 while (T--)
100 {
101 cin>>a>>b;
102 bfs();
103 if (d[b]==-1)
104 {
105 cout<<"Impossible"<<endl;
106 }
107 else
108 {
109 cout<<d[b]<<endl;
110 }
111
112 }
113
114
115 return 0;
116 }
117