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 阅读(1294) 评论(0)  编辑 收藏 引用


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