The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 3126-Prime Path 广度优先搜索BFS

不知道数论里面是不是有相关的公式，总之这道题我做的有点暴力，呵呵，一个BFS搞定；
要说具体的算法的话，就是【】【】【】【】这 四个数位按从左到右的顺序每次改变一个位置上的数字，如果这个数字是质数，就把它放入队列，并记录下到达这个数字所要经历的步数即可，然后循环搜索，搜到跳出。。。
有点遗憾的是，这道题我写的有点长，如果你有更好的想法，不妨告诉我哦 谢谢啦O(∩_∩)O~

#include <iostream>
#include <algorithm>
#include<cstdio>
using namespace std;

bool prim[10000];

struct node
{
    int n;
    int step;

}line[100001];

int visited[10000];

int main()
{
    int n,m;
    int i,j;
    for(i=2;i<=10000;i++)
    {
        if(prim[i]==true)
            continue;
        for(j=2;j<=10000;j++)
        {
            if(i*j>10000)
                break;
            prim[i*j]=true;
        }
    }



    /////////////////////////////////////////////////////////////////////////////////////////
    int testcase;
    int front;
    int rear;
    scanf("%d",&testcase);
    for(j=1;j<=testcase;j++)
    {
        memset(visited,false,sizeof(visited));
        for(i=1;i<=10000;i++)
        {
            line[i].n=0;
            line[i].step=0;
        }

        front=1;
        rear=1;
        scanf("%d%d",&n,&m);
        line[1].n=n;
        line[1].step=0;


        while(front<=rear)
        {
            if(line[front].n==m)
                break;

            if(visited[line[front].n]==0)
            {
                visited[line[front].n]=1;
                int k;
                for(k=1;;k++)
                {
                    if(line[front].n-k*1000>=1000)
                    {
                        if (prim[line[front].n-k*1000]==0&&visited[line[front].n-k*1000]==false)
                        
                        {

                        

                        rear++;
                        line[rear].n=line[front].n-k*1000;
                        line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n+k*1000<10000)

                    {
                        if(prim[line[front].n+k*1000]==0&&visited[line[front].n+k*1000]==false)
                        {

                        

                        rear++;
                        line[rear].n=line[front].n+k*1000;
                        line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;


                }
                for(k=1;;k++)
                {
                    if(line[front].n%1000-k*100>=0)
                    {
                        if(prim[line[front].n-k*100]==0&&visited[line[front].n-k*100]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n-k*100;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n%1000+k*100<1000)
                    {
                        if(prim[line[front].n+k*100]==0&&visited[line[front].n+k*100]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n+k*100;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n%100-k*10>=0)
                    {
                        if(prim[line[front].n-k*10]==0&&visited[line[front].n-k*10]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n-k*10;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n%100+k*10<100)
                    {
                        if(prim[line[front].n+k*10]==0&&visited[line[front].n+k*10]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n+k*10;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n%10-k*1>=0)
                    {
                        if(prim[line[front].n-k*1]==0&&visited[line[front].n-k*1]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n-k*1;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
                for(k=1;;k++)
                {
                    if(line[front].n%10+k*1<10)
                    {
                        if(prim[line[front].n+k*1]==0&&visited[line[front].n+k*1]==false)
                        {
                            rear++;
                            line[rear].n=line[front].n+k*1;
                            line[rear].step=line[front].step+1;
                        }
                    }
                    else
                        break;
                }
            }
        front++;
        }
        if(front>rear)
            printf("Impossible\n");
        else
            printf("%d\n",line[front].step);

    }
    system("pause");
    return 0;
}




posted on 2009-02-27 22:31 abilitytao 阅读(1308) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理