首页 > 代码库 > poj3126（bfs）

poj3126（bfs）

2024-08-08 08:31:15   218人阅读

 

题目链接：http://poj.org/problem?id=3126

题意：给两个四位数n,m,将n变成m需要多少步，要求每次只能改变n的某一位数，即改变后的数与改变前的数只有一位不同，且每次改变后的数都是素数。

分析：筛选素数+bfs，枚举每一位数字进行修改，修改后还是素数的进入队列，循环出队入队，最后改变一步、两步、三步...变成的素数散落开来，如同一棵树，遇到与要改变目标相同的数时返回步数即可。

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;unsigned long long ans,n,ok;int prime[10010];int vis[10010],step[10010];void init(){    for(int i=1000;i<10000;i++)    {        for(int j=2;j*j<=i;j++)        {            int flag=0;            if(i%j==0)            {                prime[i]=0;flag=1;break;            }            if(!flag)prime[i]=1;        }    }}int bfs(int xx,int yy){    int a[10];    memset(vis,0,sizeof(vis));    memset(step,0,sizeof(step));    queue<int>que;    que.push(xx);    vis[xx]=1;    while(!que.empty())    {        int x=que.front();que.pop();        if(x==yy)return step[x];        a[0]=x%10;a[1]=x/10%10;        a[2]=x/100%10;a[3]=x/1000;        for(int i=0;i<4;i++)        {            int num=a[i];            for(int j=0;j<10;j++)            if(j!=num)            {                a[i]=j;                int cnt=a[0]+10*a[1]+100*a[2]+1000*a[3];                if(!vis[cnt]&&prime[cnt])                {                    step[cnt]=step[x]+1;vis[cnt]=1;                    que.push(cnt);                }            }            a[i]=num;        }    }    return -1;}int main(){    int T,a,b,res;    init();    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&a,&b);        res=bfs(a,b);        if(res==-1)printf("Impossible\n");        else printf("%d\n",res);    }}
View Code

 

poj3126（bfs）


联系
我们