POJ 3126 Prime Path

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <sstream>
 5 #include <algorithm>
 6 #include <list>
 7 #include <map>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <cmath>
12 #include <cstdlib>
13 //#include <memory.h>
14 #define clc(a,b) memset(a,b,sizeof(a))
15 using namespace std;
16 const int maxn=100000;
17 const int inf=0x3f3f3f3f;
18 int n,m;
19 bool pri[10000],vis[10000];
20 int countt[10000];
21 int t[4];
22 void prim(){
23     for(int i=1000;i<10000;i++){
24         bool flag=false;
25         for(int j=2;j<i;j++)
26             if(i%j==0){
27                pri[i]=false;
28                flag=true;
29                break;
30             }
31         if(!flag)
32             pri[i]=true;
33     }
34 }
35 
36 int dfs(int a,int b){
37     queue<int>q;
38     q.push(a);
39     vis[a]=true;
40     countt[a]=0;
41     while(!q.empty()){
42         int v=q.front();
43         q.pop(); 
44         if(v==b){
45             return countt[v];
46         }
47         t[0]=v/1000;
48         t[1]=v%1000/100;
49         t[2]=v%100/10;
50         t[3]=v%10;
51         for(int i=0;i<4;i++){
52            int tem=t[i];
53            for(int j=0;j<10;j++){
54               if(j!=tem){
55                 t[i]=j;
56                 int vtemp=t[0]*1000+t[1]*100+t[2]*10+t[3];
57                 if(pri[vtemp]&&!vis[vtemp]){
58                    countt[vtemp]=countt[v]+1;
59                    vis[vtemp]=true;
60                    q.push(vtemp);
61                 }
62                 if(vtemp==b){
63                     return countt[vtemp];
64                 }
65               }
66            }
67            t[i]=tem;
68         }
69     }
70     return -1;
71 }
72 int main(){
73     // freopen("in.txt","r",stdin);
74     int ans;
75     int T;
76     while(~scanf("%d",&T)){
77         prim();
78         while(T--){
79            scanf("%d%d",&n,&m);
80            clc(vis,false);
81            clc(countt,0);
82            ans=dfs(n,m);
83            if(ans!=-1)
84             printf("%d\n",ans);
85            else
86             printf("Impossible\n");
87        } 
88     }
89     return 0;
90 }