【题目大意】

对话很坑爹，不过很有意思，直接看题干就可以了。

给你两个四位数a和b，现在要你从a经过变换得到b，并且变换的中间的每一位都要是素数，并且相邻两个素数之间只能有一个位不同。

【题目分析】

开始没想到怎么做，以为有什么高深的解法，后来经大神指点说是爆搜就可，思路才打开。

这题没什么陷阱，用爆搜时间复杂度也很低。

怎么爆搜呢？

我们将a的每个位都从0~9列举出来放入队列中，其实就是BFS，只不过是40出口的BFS，但是个位上必须将偶数除掉，顿时就少了一半的搜索量。

因为数据不是很大，所以我们可以用结构体数组来模拟队列。

BFS队列+素数判定

 

//Memory   Time//  256K       32MS#include
      
       #include
       
        using namespace std;struct Node{        int prime;        int step;};bool JudgePrime(int digit){    if(digit==2 || digit==3)        return true;    else if(digit<=1 || digit%2==0)        return false;    else if(digit>3)    {        for(int i=3;i*i<=digit;i+=2)            if(digit%i==0)                return false;        return true;    }}int a,b;bool vist[15000];Node queue[15000];void BFS(void){    int i;  //temporary    int head,tail;    head=tail=0;    queue[head].prime=a;    queue[tail++].step=0;    vist[a]=true;    while(head
        
         >test;    while(test--)    {        cin>>a>>b;        memset(vist,false,sizeof(vist));        BFS();    }    return 0;}