poj3126Prime Path（bfs）

每次四种决策，千位||百位||十位||个位。
其实各位数字不用存进结构体里，每次算一下就好
  1 #include<cstdio>
  2 #include<queue>
  3 #include<cstring>
  4 using namespace std;
  5 int c[10]={0,1,2,3,4,5,6,7,8,9};
  6 int vis[10000];
  7 int ispri[10000];
  8 struct node
  9 {
 10     int oo[4];
 11     int d;
 12     int x;
 13 }now,nex;
 14 int x,y;
 15 void trans(int* a,int x)
 16 {
 17     int i=3;
 18     while(x)
 19     {
 20         a[i--]=x%10;
 21         x/=10;
 22     }
 23 }
 24 void is()
 25 {
 26     for(int i=2;i*i<10010;i++) if(!ispri(i))
 27         for(int j=i*i;j<10010;j+=i)
 28         ispri[j]=1;
 29 }
 30 int bfs()
 31 {
 32     queue<node> q;
 33     trans(now.oo,x);
 34     now.x=x;
 35     now.d=0;
 36     q.push(now);
 37     vis[x]=1;
 38     while(!q.empty())
 39     {
 40        now=q.front();
 41        q.pop();
 42        if(now.x==y) return now.d;
 43        for(int i=1;i<10;i++)
 44        {
 45            if(c[i]!=now.oo[0])   //千位
 46             {
 47                 nex.x=c[i]*1000+now.x%1000;
 48                 if(!vis[nex.x]&&!ispri[nex.x])
 49                 {
 50                     vis[nex.x]=1;
 51                     trans(nex.oo,nex.x);
 52                     nex.d=now.d+1;
 53                     q.push(nex);
 54                 }
 55             }
 56        }
 57         for(int i=0;i<10;i++)  //百位
 58         {
 59            if(c[i]!=now.oo[1])
 60             {
 61                 nex.x=c[i]*100+now.x/1000*1000+now.x%100;
 62                 if(!vis[nex.x]&&!ispri[nex.x])
 63                 {
 64                     vis[nex.x]=1;
 65                     trans(nex.oo,nex.x);
 66                     nex.d=now.d+1;
 67                     q.push(nex);
 68                 }
 69             }
 70         }
 71          for(int i=0;i<10;i++)  //十位
 72         {    
 73             if(c[i]!=now.oo[2])
 74             {
 75                 nex.x=c[i]*10+now.x/100*100+now.x%10;
 76                 if(!vis[nex.x]&&!ispri[nex.x])
 77                 {
 78                     vis[nex.x]=1;
 79                     trans(nex.oo,nex.x);
 80                     nex.d=now.d+1;
 81                     q.push(nex);
 82                 }
 83             }
 84         }
 85         for(int i=0;i<10;i++)  //个位
 86        {
 87            if(c[i]!=now.oo[3])
 88             {
 89                 nex.x=c[i]+now.x/10*10;
 90                 if(!vis[nex.x]&&!ispri[nex.x])           
 91                  {
 92                     vis[nex.x]=1;
 93                     trans(nex.oo,nex.x);
 94                     nex.d=now.d+1;
 95                     q.push(nex);
 96                 }
 97             }
 98        }
 99     }
100 
101 }
102 
103 int main()
104 {
105     int t;
106     scanf("%d",&t);
107     memset(ispri,0,sizeof(ispri));
108     is();
109     while(t--)
110     {
111         memset(vis,0,sizeof(vis));
112         scanf("%d%d",&x,&y);
113         printf("%d
",bfs());
114     }
115 }