设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

2014 UESTC Training for Search Algorithm Problem D 方老师与素数

2014-05-05 16:42:00.0 Search Algorithm BFS prime  
导读:BFS 水题。先筛一下素数就好。//方老师与素数#include#include#include#includeusing namespace std;bool prime[10001];bool vis[10001];int n,m;int bfs(){ queueq; q.push(n); q.push(-1); int ans=0; while(!q.empty...。。。

BFS 水题。

先筛一下素数就好。

//方老师与素数#include#include#include#includeusing namespace std;bool prime[10001];bool vis[10001];int n,m;int bfs(){    queueq;    q.push(n);    q.push(-1);    int ans=0;    while(!q.empty())    {        int tmp=q.front();        if(tmp==-1)        {            q.pop();            if(q.empty())            return -1;            ans++;            q.push(tmp);continue;        }q.pop();        if(tmp==m)return ans;        int s;        for(int i=1;i<=9;i++)        {            s=tmp%1000+i*1000;            if(!vis[s]&&!prime[s])            vis[s]=1,q.push(s);        }        for(int i=0;i<=9;i++)        {            s=tmp/1000*1000+tmp%100+i*100;            if(!vis[s]&&!prime[s])            vis[s]=1,q.push(s);        }        for(int i=0;i<=9;i++)        {            s=tmp/100*100+tmp%10+i*10;            if(!vis[s]&&!prime[s])            vis[s]=1,q.push(s);        }        for(int i=0;i<=9;i++)        {            s=tmp/10*10+i;            if(!vis[s]&&!prime[s])            vis[s]=1,q.push(s);        }    }    return -1;}int main(){    prime[1]=1;    for(int i=2;i<10001;i++)    for(int j=2;i*j<10001;j++)    prime[i*j]=1;    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        memset(vis,0,sizeof(vis));        int tmp=bfs();        if(tmp==-1)        puts("Impossible");        else        printf("%d\n",tmp);    }}


(编辑: dongshimou)

网友评论
相关文章