#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
using namespace std;

#define mem(a) memset(a,0,sizeof(a))
#define ll long long
const int maxn = 100100;
const int inf = 0x3f3f3f3f;
int t,n,m;
bool vis[10000];
set<int> a;
void init()
{
    int i,j,k=0;
    for(i = 1001; i < 10000; i+=2)
    {
        for(j = 2; j <= sqrt(i); j++)
        {
            if(i%j == 0) break;
        }
        if(j > sqrt(i)) a.insert(i);
    }
}

struct node
{
    int num,step;
};

void bfs()
{
    mem(vis);
    node x,y;
    vis[n] = 1;
    x.num = n,x.step = 0;
    queue <node> q;
    q.push(x);
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        if(x.num == m)
        {
            printf("%d\n",x.step);
        }
        int ge  = x.num-x.num%10;
        int shi = x.num - (x.num%100-x.num%10);
        int bai = x.num - (x.num%1000/100)*100;
        int qi  = x.num%1000;
        for(int i = 1; i <10 ; i+=2)
        {
            y.num = ge+i;
            if(a.count(y.num) && !vis[y.num])
            {
                y.step = x.step+1;
                vis[y.num] = 1;
                q.push(y);
            }
        }
        for(int i = 0; i <10 ; i++)
        {
            y.num = shi+i*10;
            if(a.count(y.num) && !vis[y.num])
            {
                y.step = x.step+1;
                vis[y.num] = 1;
                q.push(y);
            }
        }
        for(int i = 0; i <10 ; i++)
        {
            y.num = bai+i*100;
            if(a.count(y.num) && !vis[y.num])
            {
                y.step = x.step+1;
                vis[y.num] = 1;
                q.push(y);
            }
        }
        for(int i = 1; i <10 ; i++)
        {
            y.num = qi+i*1000;
            if(a.count(y.num) && !vis[y.num])
            {
                y.step = x.step+1;
                vis[y.num] = 1;
                q.push(y);
            }
        }
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        bfs();
    }
    return 0;
}

• Re:我也是,真的懵逼 (2519) ZangYuanHao 2021-01-06 17:47:08