题目

http://poj.org/problem?id=3126

思路

素数筛给出4位素数，双向 BFS

源码

//
//  3126.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//  Copyright © 2020 bytedance. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
bool pre[10000]={false};
vector<string> p;
int main(){
    int time;
    cin >> time;

    string s,e;
    for(int i = 2;i <= 9999;++i){
        for(int j = i*2;j<=9999;j+=i)pre[j]=true;
    }
    for(int i = 1000;i<=9999;++i){
        if(!pre[i])p.push_back(to_string(i));
    }
    while(time--){
        cin >> s>>e;
        //素数集合构造完毕
        int idx = 0;
        queue<string> q[2];
        map<string,bool> vis[2];
        q[0].push(s);
        q[1].push(e);
        vis[0][s]=true;
        vis[1][e]=true;
        int cnt = 0;
        bool f = true;
        while(!q[0].empty()&&!q[1].empty()&&f){
            idx=idx^1;
            int sz = q[idx].size();
            while(sz--&&f){
                string crt = q[idx].front();
                q[idx].pop();
                if(vis[idx^1][crt]==true){ cout<< cnt; f=false;}
                for(int i = 0;i < 4&&f;++i){
                    char c = crt[i];
                    for(int j = '0';j <='9'&&f;++j){
                        crt[i] = j;
                        if(j==c||vis[idx][crt]||find(p.begin(),p.end(),crt)==p.end())continue;
                        q[idx].push(crt);
                        vis[idx][crt]=true;
                    }
                    crt[i] = c;
                }
            }
            cnt++;
        }
    }
    return 0;
}