Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:代码较简洁，交流下

Posted by 2014302384 at 2015-08-17 14:07:02 on Problem 3126
In Reply To:代码较简洁，交流下 Posted by:on_pku at 2009-12-21 18:20:42
```> //6266010 on_pku 3126 Accepted 732K 16MS G++ 2214B 2009-12-21 18:18:46
> #include<iostream>
> #include<cstdlib>
> #include<cstdio>
> #include<queue>
> using namespace std;
> const int SIZE = 10000;
> bool prime[SIZE];
> int step[SIZE];
> int base[4] = {1,10,100,1000};
> int main()
> {
>         for(int i = 0; i < SIZE; i++)prime[i] = true;
>
>         for(int i = 2; i < SIZE; i++){
>                 if(prime[i]){
>                              for(int j = 2; i*j < SIZE; j++)
>                                      prime[i*j] = false;
>                 }
>         }
>
>         int t,a,b,d[4];
>         scanf("%d",&t);
>         while(t--){
>                    scanf("%d %d",&a,&b);
>                    fill(step,step+SIZE,0);
>                    queue<int>path;
>                    path.push(a);
>                    step[a] = 1;
>                    while(!path.empty()){
>                          int ori = path.front();
>                          if(ori == b)break;
>                          path.pop();
>                          d[0] = ori%10;  d[1] = ori%100/10;
>                          d[2] = ori%1000/100;  d[3] = ori/1000;
>                          int newnum;
>                          for(int i = 0; i < 10; i ++){
>                                  newnum = ori - d[3]*1000 + i*1000;
>                                  if(i != 0 && prime[newnum] && !step[newnum]){
>                                       step[newnum] = step[ori] + 1;
>                                       path.push(newnum);
>                                  }
>                                  for(int k = 0; k < 3; k++){
>                                          newnum = ori - d[k]*base[k] + i*base[k];
>                                          if(prime[newnum] && !step[newnum]){
>                                               step[newnum] = step[ori] + 1;
>                                               path.push(newnum);
>                                          }
>                                  }
>                          }
>                    }
>                    printf("%d\n",step[b]-1);
>         }
>         return 0;
> }
```

Followed by:

User ID:
Title:

Content: