【POJ-3126】解题报告（BFS，换门牌号，素数筛）

原始题目

Prime Path

  • Time Limit: 1000MS
  • Memory Limit: 65536K
  • Total Submissions: 24280
  • Accepted: 13417

Problem Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.

— It is a matter of security to change such things every now and then, to keep the enemy in the dark.

— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!

— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.

— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!

— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.

— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.

— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.

— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?

— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033

1733

3733

3739

3779

8779

8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

Source

Northwestern Europe 2006

题目大意

换门牌号，要求每次只能更换一位，且更换完之后的新数字要是素数，问更换到指定号码的最少步数是多少。

解题思路

按个十百千位广搜，<40入口，搜索的规则是，该数没有被搜索过，且该数为素数。由于是BFS，所以第一次搜索到最终更改的门牌号时一定是最少步数，输出该值即可。如果广搜入口全部遍历一编还是未能搜索到最终更改的门牌号，即为不可能，输出Impossible。

要点：

  1. 由于要求是素数，所以个位只需要搜索奇数即可，以及千位避开0；

  2. 涉及素数，可以用最基础的素数判断（即从2开始逐个除，若有因子则返回false），或者使用素数筛先建立素数表然后直接查表（待补充）

解题代码

  • 素数传统判断
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include<algorithm>
#define maxn 10100
using namespace std;
int n,m; 
bool vis[maxn]; // 访问标记
//int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量
//int dir[8][2]={{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}} ;
struct State // BFS 队列中的状态数据结构
{
	int x;
	int Step_Counter; // 搜索步数统计器
};
bool isPrime(int x)
{
	if(x==0||x==1)
		return false;
	else if(x==2||x==3)
		return true;
	else
	{
		for(int i=2;i<=(int)sqrt(x);i++)
		{
			if(x%i==0)
				return false;
		}
		return true;
	}
} 

State a[maxn];

bool CheckState(int s,State now) // 约束条件检验
{
	if(s!=now.x&&!vis[s]&&isPrime(s)) // 满足条件	
	{
//		printf("next s=%d, step=%d\n",s,now.Step_Counter+1);
		return 1;
	}	
	else // 约束条件冲突
		return 0;
}

void bfs(State st)
{
	queue <State> q;
	State now,next; // 定义2个状态，当前和下一个
	st.Step_Counter=0; // 计数器清零
	q.push(st); // 入队	
	vis[st.x]=1; // 访问标记
	while(!q.empty())
	{
		now=q.front(); // 取队首元素进行扩展
		if(now.x==m) // 出现目标态，此时为Step_Counter 的最小值，可以退出即可
		{
			printf("%d\n",now.Step_Counter);
			return;
		}
		//按照规则搜索下一组数
		for(int i=1;i<=9;i+=2)
		{
			int s=now.x/10*10+i;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next); 
			}
		}
		for(int i=0;i<=9;i++)
		{
			int s = now.x / 100 * 100 + i * 10 + now.x % 10;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next);
			}
		}
		for(int i=0;i<=9;i++)
		{
			int s=now.x/1000*1000+i*100+now.x%100;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next);
			}
		}
		for(int i=1;i<=9;i++)
		{
			int s=i*1000+now.x%1000;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next); 
			} 
		}
		q.pop(); // 队首元素出队
	}
	printf("Impossible\n");
 	return;
}

int main()
{
	int t;
	scanf("%d",&t);
		for(int i=0;i<t;i++)
		{
//			printf("%d  %d\n",t,n);
//			while(!q.empty()) q.pop();
			memset(vis,0,sizeof(vis));
			scanf("%d%d",&n,&m);
			struct State tmp;
			tmp.x=n;
			tmp.Step_Counter=0;
			bfs(tmp);
		}
	return 0;
}
  • 非线性埃式素数筛
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include<algorithm>
#define maxn 10100
using namespace std;
int n,m; 
bool vis[maxn]; // 访问标记
//int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量
//int dir[8][2]={{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}} ;
struct State // BFS 队列中的状态数据结构
{
	int x;
	int Step_Counter; // 搜索步数统计器
};
bool isPrime[maxn]; 
void solvePrime()  //埃式素数筛 
{
	memset(isPrime,1,sizeof(isPrime));
	isPrime[0]=isPrime[1]=false;
	for(int i=2;i<=maxn;i++)
	{
		if(isPrime[i])
		{
			for(int j=i*i;j<=maxn;j+=i)
			{
				isPrime[j]=false;
			}
		}
	}
}

State a[maxn];

bool CheckState(int s,State now) // 约束条件检验
{
	if(s!=now.x&&!vis[s]&&isPrime[s]) // 满足条件	
	{
//		printf("next s=%d, step=%d\n",s,now.Step_Counter+1);
		return 1;
	}	
	else // 约束条件冲突
		return 0;
}

void bfs(State st)
{
	queue <State> q;
	State now,next; // 定义2个状态，当前和下一个
	st.Step_Counter=0; // 计数器清零
	q.push(st); // 入队	
	vis[st.x]=1; // 访问标记
	while(!q.empty())
	{
		now=q.front(); // 取队首元素进行扩展
		if(now.x==m) // 出现目标态，此时为Step_Counter 的最小值，可以退出即可
		{
			printf("%d\n",now.Step_Counter);
			return;
		}
		//按照规则搜索下一组数
		for(int i=1;i<=9;i+=2)
		{
			int s=now.x/10*10+i;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next); 
			}
		}
		for(int i=0;i<=9;i++)
		{
			int s = now.x / 100 * 100 + i * 10 + now.x % 10;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next);
			}
		}
		for(int i=0;i<=9;i++)
		{
			int s=now.x/1000*1000+i*100+now.x%100;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next);
			}
		}
		for(int i=1;i<=9;i++)
		{
			int s=i*1000+now.x%1000;
			if(CheckState(s,now))
			{
				vis[s]=1;
				next.x=s;
				next.Step_Counter=now.Step_Counter+1;
				q.push(next); 
			} 
		}
		q.pop(); // 队首元素出队
	}
	printf("Impossible\n");
 	return;
}

int main()
{

	solvePrime();
	int t;
	scanf("%d",&t);
		for(int i=0;i<t;i++)
		{
//			printf("%d  %d\n",t,n);
//			while(!q.empty()) q.pop();
			memset(vis,0,sizeof(vis));
			scanf("%d%d",&n,&m);
			struct State tmp;
			tmp.x=n;
			tmp.Step_Counter=0;
			bfs(tmp);
		}
	return 0;
}

收获与反思

题目本身没什么问题，两次TLE都是因为输入输出格式的问题最后一直等待输入，需要再细心一点。

对于素数筛知识的补充。

  1. 传统方法：根据是否有大于1小于本身的因子来判断，复杂度为O(nlognlogn) （虽然还不会证明）。

  2. 素数筛方法

    埃式筛法，即埃拉托斯特尼筛法，本题采用。原理就是排除0，1，从2开始当前未筛去的数最小的数即为素数

改进前后两次的时间对比（图待补充）

另外还有欧拉筛法（线性）有待学习。