POJ - 3126 - Prime Path

Question

题目大意

第一个数 T 代表测试样例个数，下面每一行是一个测试样例，每行输入两个数 a 、 b ，这两个数都是 1000~9999 之间的素数，现在要求你从第一个数变成第二个数，每次变换可以（只可以) 改变其中的一个数字，而且改变之后的那个数必须是素数，问能否经过有限次的这样变化，将第一个素数 a 变成第二个素数 b ，要你求最少的变化步数。

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

解析

相当于求无权图的最短路径（有权图用 dijkstra )，用 BFS 即可。

• 筛素数可以使用 埃拉托斯特尼筛法 ，这个在 bfs 判断下一个节点进入队列时使用；
• 然后主要就是每次变化四个数，每个数从 0~9 之间变化，得到下一个节点，然后判断是否满足条件，如果满足条件进队列即可。

import java.util.*;
import java.io.*;

public class Main {

    static class Clazz {
        public int num;
        public int step;

        public Clazz(int num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    static final int MAX = 10000;

    static boolean[] sieve() {
        boolean[] is_prime = new boolean[MAX];
        Arrays.fill(is_prime, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i < MAX; i++) {
            if (is_prime[i]) {
                for (int j = i * i; j < MAX; j += i)
                    is_prime[j] = false;
            }
        }
        return is_prime;
    }

    static int[] separate(int num) {
        int[] arr = new int[4];
        int i = 0;
        while (num > 0) {
            arr[i++] = num % 10;
            num /= 10;
        }
        return arr;
    }

    static int revert(int[] sep) {
        int res = 0;
        for (int i = 0; i < sep.length; i++)
            res += sep[i] * (int) Math.pow(10, i);
        return res;
    }

    static int bfs(int s, int e, boolean[] is_prime, boolean[] vis) {
        Queue<Clazz> queue = new LinkedList<Clazz>();
        queue.add(new Clazz(s, 0));
        vis[s] = true; // 和 dijkstra 不同, bfs 一开始标记为 true
        int[] aArr, bArr; // 两个数组
        while (!queue.isEmpty()) {
            Clazz cur = queue.poll();
            if (e == cur.num) {
                return cur.step;
            }
            aArr = separate(cur.num);
            for (int i = 0; i < 4; i++) {
                bArr = Arrays.copyOf(aArr, aArr.length);
                for (int j = 0; j < 10; j++) {
                    bArr[i] = j;
                    int nxtNum = revert(bArr);
                    if (nxtNum > 1000 && nxtNum < 10000 && nxtNum != cur.num && !vis[nxtNum] && is_prime[nxtNum]) {
                        vis[nxtNum] = true;
                        queue.add(new Clazz(nxtNum, cur.step + 1));
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int T = cin.nextInt();
        while (T-- > 0) {
            int s = cin.nextInt();
            int e = cin.nextInt();
            boolean[] is_prime = sieve(); // 筛选 0~10000 的素数
            boolean[] vis = new boolean[MAX];
            int res = bfs(s, e, is_prime, vis);
            System.out.println(res == -1 ? "Impossible" : res);
        }
    }
}