POJ 3126 Prime Path 素数打表+BFS

发表于 | 分类于 | 阅读次数:
字数统计: 451 字

题目链接：http://poj.org/problem?id=3126

题意

给出一次操作的定义，将一个四位数的一位转换成另外一位数字（不含前导0）。同时给出两位素数，求中间需要进过多少次这样的操作才能够从开始的哪一位素数达到后面的那一位素数，而且必须满足中间进过的数都是素数.

题解

  • 使用BFS搜索路径，同时记录搜索路径的长度
  • 用结构体将一个数和搜索到这个数是已经走过的步数绑定起来
  • 数字用string表示，便于进行操作，只需对对应的字符进行操作即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int maxn=10005;
const int maxp=10005;
bool is_prime[maxp];
int prime[maxp],num;
int visit[maxn];
struct poin
{
	string num;
	int step;
	poin(string num,int step):num(num),step(step) {}
};

void init()    //欧拉筛选素数打表
{
	num=0;
    memset(is_prime,true,sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<maxp;i++)
	{
		if(is_prime[i]) prime[num++]=i;
		for(int j=0;j<num && i*prime[j]<maxp;j++)
		{
			is_prime[i*prime[j]]=false;
			if(i%prime[j]==0) break;
		}
	}
}

void solve()
{
	int t;
	cin>>t;
	string a,b;
	while(t--)
	{
		cin>>a>>b;
		int ans=-1;
		init();
		memset(visit,0,sizeof(visit));
		queue<poin> que;
		que.push(poin(a,0));
		while(!que.empty())
		{
			poin p=que.front();
			que.pop();
			if(p.num==b)
			{
				ans=p.step;
				break;
			}
			for(int i=3;i>=0;i--)
			{
				int be= (i==0)?1:0;
				string c=p.num;
				for(int j=be;j<10;j++)
				{
					c[i]=j+'0';
					int next=atoi(c.c_str());
					if(!visit[next] && is_prime[next] &&c!=p.num)  //防止出不来了
					{
						//cout<<c<<endl;
						visit[next]=1;
						que.push(poin(c,p.step+1));
					}
				}
			}
		}
		cout<<ans<<endl;
	}
}