Sicily 1444 Prime Path (SOJ 1444)「BFS 广度优先搜索」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/120

原题地址:点击打开链接

乍看此题,感觉有点吓人,我天生对涉及素数的题目有恐惧感,然后觉得Prime这个单词在此题中双关的很好······不错不错,题目蛮有意思的。

最近要开始准备保研了,手头也有两个小项目不得不认真动工,所以留给刷题的时间可能就少了。还没有完全看过《算法导论》,《数据结构与算法分析——C++描述》,《HeadFirst Java》,之前一直想看的黑书《算法艺术与信息学竞赛》可能也要推迟了,到现在才觉得人生好像充满了意义,为什么呢,因为之前一段时间被鄙视被虐了,现在奋发图强了。

接下来的一段时间,就优先看《编程之美》,优先搞掂两个小项目,优先——把《离散数学及其应用》全部吃完大哭,不过离散数学这本书,貌似蛮有意思的,对编程的帮助应该很大。

——————正文——————

我有个习惯,在睡觉前如果脑子里面没有题目的话,就把一题放到脑子里面然后躺在床上想一下,有头绪了第二天就动手写。

我在场上发现这题其实就是一个十分中规中矩的广搜。按照题目,你只要找到1000~9999之中的素数,然后把每个素数当作一个节点,可以互相转变的素数就相当于两个节点有无向边相连。所以先把图建立起来。

找出素数很简单,使用递推就可以很快将10000以内的素数全部找出来。

用for循环遍历每一个素数,遍历的时候使用一个数组w[4]存储各个位置的数。

例如对于1033,存储的内容为:w[0]=3*1,w[1]=3*10,w[2]=0*100,w[3]=1*1000

那么其数字上”相邻“的数,可以通过k+w[1]+w[2]+w[3],w[0]+k+w[2]+w[3],w[0]+w[1]+k+w[3] 或者w[0]+w[1]+w[2]+k获得,其中0<=k<=9

然后选出其中的素数,建立邻接关系即可。(邻接表我通常喜欢用vector实现)

最后就是很常规的bfs了,直接上代码。

#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<queue>
#include<cmath>
#include<vector>
#define BOUND 10005
using namespace std;
bool ap[10005];//anti-prime,i为素数则ap[i]=false,否则a[i]=true
int n,a,b;
struct node
{
	int ii;
	int dis;
	node(int i,int d)
	{
		ii=i;
		dis=d;
	}
};
queue<node> q;
vector<int> v[BOUND];
bool isv[BOUND];
void bfs()
{
	int tmp,res=-1;
	memset(isv,0,sizeof(isv));
	while(!q.empty())
		q.pop();
	q.push(node(a,0));
	isv[a]=true;
	node tn(0,0);
	while(!q.empty() && res==-1)
	{
		tn=q.front();
		q.pop();
		for(int i=0;i<v[tn.ii].size();++i)
		{
		  tmp=v[tn.ii][i];
			if(isv[tmp])
			 continue;
			isv[tmp]=true;
			if(tmp==b)
			{
				res=tn.dis+1;
				break;
			}
			q.push(node(tmp,tn.dis+1));
		}
	}
	
	if(res==-1)
	 printf("Impossible\n");
	else
	 printf("%d\n",res);
}
int main()
{
	 //freopen("in","r",stdin);
	 //freopen("out","w",stdout);
	 for(int i=4;i<BOUND;i+=2)
		ap[i]=true;
	 for(int i=3;i<BOUND;i+=2)
	  if(!ap[i])
		for(int j=i;j<BOUND/i;j+=2)
		  ap[i*j]=true;
	
	 for(int i=1000;i<BOUND;++i)
	 {
		    if(ap[i])
			 continue;
			int w[4]; int tmp=0;
			w[3]=i;
			while(tmp<3)
			{
				w[tmp]=(w[3]%10)*pow(10,tmp);
				tmp++;
				w[3]/=10;
			}
			w[3]*=1000;
			for(int j=0;j<=3;j++)
			{
			 tmp=i-w[j];
			 const int pp=pow(10,j);
			 for(int k=0*pp;k<=9*pp;k+=pp)
			  if(i!=(tmp+k) && !ap[tmp+k])
			    v[i].push_back(tmp+k);
			}
	 }
	
	 scanf("%d",&n);
	 while(n--)
	 {
		 scanf("%d%d",&a,&b);
		 if(a==b)
		 {
			 printf("0\n");
			 continue;
		 }
		 bfs();
	 }
}

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注