}

【例2】质数变换（POJ 3126 “Prime Path”）

      给定两个四位质数a和b，要求把a变换到b。变换的过程要求：（1）每次变换出来的数都是一个四位质数；（2）每一步变换所得的质数与前一步得到的质数只能有一个位不同。

      编写程序求从a到b最少需要的变换次数，无法变换则输出Impossible。

      例如，从1033变换到8179最少需要6歩，具体变换过程为1033、1733、3733、3739、3779、8779、8179。

      （1）编程思路。

      定义数组char prime[10000];来进行质数的判断，prime[x]=‘1’表示整数x是质数，prime[x]=‘0’表示整数x不是质数。采用筛法构建质数判定表prime[10000]。 

      在整数x进行变换时，可分别对x的千位、百位、十位和个位进行 （可用循环for (i=0;i<4;i++) 处理），每位上可由0~9这10种选择（可用循环 for (j=0;j<10;j++)处理）。即数的变换可以采用一个二重循环处理。若变换出的整数num如果是一个4位数（num>=1000），且没有访问过（visit[num]=-1），还是质数（prime[num]='1'），则将产生的整数num入队。

      （2）源程序及运行结果。

#include <iostream> 

using namespace std;

char prime[10000];

void GetPrime()              // 用筛法构建质数判定表 

{

      int i,j;

      for (i=2;i<10000;i++)

              prime[i]='1';

       for(i=2;i<10000;i++)    

       {

             if (prime[i]=='1')

                     for (j=2*i;j<10000;j+=i)

                            prime[j]='0';

         }

        prime[1]='0'; 

}

void BFS(int k,int m)

{

    int visit[10000],que[10000],a[4]={1,10,100,1000};

    int front,rear,i,j,s,x,y,num;

    for (i=1000;i<10000;i++)

              visit[i]=-1;

    front=rear=0;

    que[rear++]=k;              // k入队  

    visit[k]=0;

    while(front!=rear)

    {

           s=que[front++];         // 队头元素出队

           if (s==m)

           {

                     cout<<visit[s]<<endl;

                     return;

           }

           for (i=0;i<4;i++)

          { 

              for (j=0;j<10;j++)

              {

              x=s/(a[i]*10);