POJ3126 Prime Path

题目链接：https://vjudge.net/problem/POJ-3126
Description
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033 1733 3733 3739 3779 8779 8179 The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input

3 1033 8179 1373 8017 1033 1033

Sample Output

6 7 0

题目大意：给出两个四位的素数a，b。
a可以通过改变某一位上的数字使其变成c，但只有当c也是四位的素数时才能进行这种改变。对于每个样例，输出最少变换次数，如果无法变换成b则输出"Impossible"。

解题思路：利用BFS对素数的各位进行替换，替换后的数为素数时才压入队列，这样找出的次数即为最少次数。
Cpp Code

#include<iostream> #include<queue> #include<cmath> #include<cstring> using namespace std; bool vis[10010], is_primer[10010];//标记数组 int step[10010];//转换步数 bool Is_pri(int x){//判断素数 for (int i = 2; i <= sqrt(x*1.0);i++){ if(x%i==0){ return 0; } } return 1; } int bfs(int xx,int y){ memset(vis, 0, sizeof(vis));//初始化 memset(step, 0, sizeof(step)); int a[4]; queue<int> q; vis[xx] = 1;//访问后标记 q.push(xx); while(!q.empty()){ int x = q.front(); q.pop(); if(x==y){ return step[x]; } a[0] = x / 1000; a[1] = (x / 100) % 10; a[2] = (x / 10) % 10; a[3] = x % 10; for (int j = 0; j < 4;j++){//一位一位的替换 int num = a[j]; for (int i = 0; i < 10;i++){ if(i!=num){//选取不是原来的数进行替换 a[j] = i; int sum = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3]; if(!vis[sum]&&is_primer[sum]){ vis[sum] = 1; q.push(sum); step[sum] = step[x] + 1; } } } a[j] = num; } } return -1; } int main(){ for (int i = 1000; i < 10000;i++){ is_primer[i] = Is_pri(i); } int n; cin >> n; while (n--) { int a, b; cin >> a >> b; if(bfs(a,b)==-1){ cout << "Impossible" << endl; } else{ cout << bfs(a, b) << endl; } /* code */ } return 0; }

Java Code

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static int maxn=(int)1e5+10; static boolean vis[]=new boolean[maxn];//标记数组 static boolean isprim[]=new boolean[maxn];//素数标记数组 static void Era(int n) {//Eratosthenes筛法 for(int i=2;i<=n;i++) { if(!vis[i]) { isprim[i]=true; vis[i]=true; for(int j=(i+i);j<=n;j+=i) { vis[j]=true; } } for(int k=0;k<1000;k++) {//只能转换成4位数 isprim[k]=false; } } } static class node{ int x; int step;//转换步数 node(){} node(int a,int b){ x=a; step=b; } } public static int BFS(int x,int y) { for(int i=0;i<maxn;i++) {//初始化 vis[i]=false; } int a[]=new int[4]; Queue<node> q=new LinkedList<node>(); q.offer(new node(x,0)); vis[x]=true; while(!q.isEmpty()) { node now=q.poll(); if(now.x==y) { return now.step; } x=now.x; a[0] = x / 1000; a[1] = (x / 100) % 10; a[2] = (x / 10) % 10; a[3] = x % 10; for (int j = 0; j < 4;j++){ int num = a[j]; for (int i = 0; i < 10;i++){ if(i!=num){ a[j] = i; int sum = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3]; if(!vis[sum]&&isprim[sum]){ //System.out.println(sum); vis[sum] = true; q.offer(new node(sum,now.step+1)); } } } a[j] = num; } } return -1; } public static void main(String[] args) { Era(maxn-1); Scanner sc=new Scanner(System.in); int n,a,b; n=sc.nextInt(); while((n--)>0) { a=sc.nextInt(); b=sc.nextInt(); int ans=BFS(a,b); if(ans==-1) { System.out.println("Impossible"); } else { System.out.println(ans); } } } }