经典广搜题目

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

题意:从一个四位素数到另一个四位素数,每次变换一个数字,变换之后仍为素数,最少的步骤。

比如:1033  8179

变换过程:

1033
1733
3733
3739
3779
8779
8179

最少步骤一共是6步。

具体代码如下:

 

Accepted 296K 157MS

#include<iostream>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
queue<int> q;
int n,a,b;
bool flag[10000],flag1[10000];

void prime() /*把1000—9999的素数先一次性求出来,用flag1标记那个位置是否是素数*/
{
       int i,j,k;
       for(i=1001;i<10000;i+=2)
      {
            k=sqrt(i*1.0);
            for(j=2;j<=k;j++)
                 if(i%j==0)
                        break;
           if(j>=k+1)
                 flag1[i]=1;
     }
}

int str_int(int m,int i,int j,int k)/*变换函数*/
{
       char str[5];
       str[0]=m/1000+48;/*整数转换为字符串*/
       str[1]=m%1000/100+48;
       str[2]=m%1000%100/10+48;
       str[3]=m%1000%100%10+48;
       str[4]='\0';
       str[k]=i+48;
       m=atoi(str);  /*字符串转换为整数*/
       return m;
}
int main()
{
       cin>>n;
       prime();
       while(n–)
       {
              int T=1,i,j,k,p1,p2,ans=0;
              cin>>a>>b;
              while(!q.empty()) /*判空*/
                     q.pop();
              while(T)
              {
                      int len;
                      memset(flag,0,sizeof(flag));/*初始化flag数组为0*/
                      q.push(a);
                      len=q.size();
                     ans++;
                     for(i=1;i<=len;i++)
                     {
                             p1=q.front();
                             q.pop();  /*出队列*/
                             if(p1==b)
                             {
                                   T=0;
                                    break;
                             }
                     for(j=1;j<=9;j++)/*变换千位,不能是零*/
                     {
                            p2=str_int(p1,j,0,0);
                            /*如果flag1为真,证明是素数,如果flag为真,证明已经找过了,下同*/
                            if(p2!=p1&&flag1[p2]&&!flag[p2])
                            {
                                     q.push(p2);
                                      flag[p2]=1;
                            }
                     }
                     for(j=1;j<=3;j++)/*变换百,十,个位,从0到9*/
                             for(k=0;k<=9;k++)
                             {
                                        p2=str_int(p1,k,0,j);
                                        if(p2!=p1&&flag1[p2]&&!flag[p2])
                                        {
                                                 q.push(p2);
                                                 flag[p2]=1;
                                        }
                             }
                    }
           }
           cout<<ans-1<<endl;/*输出结果*/
     }
     return 0;
}

 

 

发表评论

电子邮件地址不会被公开。

Post Navigation