POJ 3126：Prime Path（简单搜索BFS）

题目链接

题意：
每组给定两个四位数n，m；其中n和m都是素数；每次操作能改变某一位的数字，求最少需要多少步能是从n到m，而且每次操作后得到的数字都必须为素数

题解：
很明显的BFS，但是开始由于脑袋没有想太清楚，一直没能AC
其实只需要判断个十百千位的情况，判断得到的数是不是素数和是不是已经用过了即可

代码很简单易懂

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<map>
#define lowbit(x) x&(-x)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000
using namespace std;
const double pi=acos(-1.0);
const int maxn=1e5;
const double eps=1e-8;
int t;
int n,m;
int flag;
bool vis[10010];             //判断素数
int check[maxn+10];         //判断该数是不是已经用过
//素数筛（埃氏筛）
void init(){
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<=maxn;i++){
        for(int j=i*2;j<=maxn;j+=i){
            vis[j]=false;
        }
    }
    return ;
}
struct node{
    int x;
    int step;
    node(int xx,int s){
        x=xx;
        step=s;
    }
};
void bfs(int num,int step){
    check[num]=1;
    queue<node>q;
    q.push(node(num,step));
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.x==m){
            printf("%d\n",now.step);
            flag=1;
            return ;
        }
        for(int i=0;i<=9;i++){         //个位
            int fx=(now.x/10)*10+i;
            if(check[fx]==0&&vis[fx]==true){
                q.push(node(fx,now.step+1));
                check[fx]=1;
            }
        }
        for(int i=0;i<=9;i++){         //十位
            int fx=(now.x/100)*100+i*10+now.x%10;
            if(check[fx]==0&&vis[fx]==true){
                q.push(node(fx,now.step+1));
                check[fx]=1;
            }
        }
        for(int i=0;i<=9;i++){         //百位
            int fx=(now.x/1000)*1000+i*100+now.x%100;
            if(check[fx]==0&&vis[fx]==true){
                q.push(node(fx,now.step+1));
                check[fx]=1;
            }
        }
        for(int i=1;i<=9;i++){         //千位
            int fx=i*1000+now.x%1000;
            if(check[fx]==0&&vis[fx]==true){
                q.push(node(fx,now.step+1));
                check[fx]=1;
            }
        }
    }
    return ;
}
int main(){
    init();
    scanf("%d",&t);
    while(t--){
        flag=0;
        memset(check,0,sizeof(check));
        scanf("%d%d",&n,&m);
        bfs(n,0);
        if(flag==0){
            printf("Impossible\n");
        }
    }
    return 0;
}