poj 3126 BFS

柔情只为你懂 2021-12-17 02:57 296阅读 0赞

BFS得到的一定是最短路径。开始我还在纠结怎么才是最短的呢。其实BFS的题目有个共性（这不废话，哪一类题没有共性啊。呵呵）。以后做这种题自己慢慢总结吧。

这题的思路就是写枚举出4位数的所有prime number，用个数组p\[\]标记。再用个数组visit\[\]标记某个数是否被访问过，避免重复访问.然后就是对这四位数的每一位进行BFS啦！

#include <iostream>
    #include <cstdio>
    #include <queue>
    #include <fstream>
    #include <memory.h>
    
    using namespace std;
    
    int p[10000],visit[10000];
    int n,a,b;
    int Index[4];
    struct node
    {
        
    int num,step;
    }ans[10000];
    
    bool prime(int n)
    {
        
    for(int i=2; i*i<=n ; i++)
        {
        
    if(n%i==0)
    return false;
        }
    return true;
    }
    
    int bfs()
    {
        
    int j=0,i;
        queue<node> q;
        ans[j].num=a;
        ans[j].step=0;
        visit[a]=1;
        q.push(ans[j]);
    while(!q.empty())
        {
        
            node next;
            next=q.front();
            q.pop();
    if(next.num==b)
            {
        
    return next.step;
            }
            Index[0]=next.num/1000; Index[1]=(next.num%1000)/100;
            Index[2]=(next.num%100)/10; Index[3]=next.num%10;
    for(i=0 ; i<10 ;i++)
            {
        
    if(i==Index[3])
    continue;
    int l=next.num+i-Index[3];
    if(!visit[l] && p[l])
                {
        
                    ans[++j].num=l;
                    ans[j].step=next.step+1;
                    visit[l]=1;
                   q.push(ans[j]);
                }
            }
    for(i=0 ; i<10 ;i++)
            {
        
    if(i==Index[2])
    continue;
    int l=next.num+(i-Index[2])*10;
    if(!visit[l] && p[l])
                {
        
                    ans[++j].num=l;
                    ans[j].step=next.step+1;
                   visit[l]=1;
                    q.push(ans[j]);
                }
            }
    for(i=0 ; i<10 ;i++)
            {
        
    if(i==Index[1])
    continue;
    int l=next.num+(i-Index[1])*100;
    if(!visit[l] && p[l])
                {
        
                    ans[++j].num=l;
                    ans[j].step=next.step+1;
                    visit[l]=1;
                   q.push(ans[j]);
                }
            }
    for( i=0 ; i<10 ;i++)
            {
        
    if(i==Index[0])
    continue;
    int l=next.num+(i-Index[0])*1000;
    if(!visit[l] && p[l])
                {
        
                    ans[++j].num=l;
                    ans[j].step=next.step+1;
                    visit[l]=1;
                    q.push(ans[j]);
                }
            }
    
        }
    
    }
    
    int main()
    {
        
        freopen("acm.txt","r",stdin);
        memset(p,0,sizeof(p));
        scanf("%d",&n);
    for(int i=1000; i<10000; i++)
        {
        
    if(prime(i))
              p[i]=1;     //is prime number
        }
    while(n--)
        {
        
            memset(visit,0,sizeof(visit));
            scanf("%d%d",&a,&b);
            printf("%d\n",bfs());
        }
    return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/03/14/2397114.html