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

## 代码较简洁，交流下

Posted by on_pku at 2009-12-21 18:20:42 on Problem 3126
```//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: