POJ 3126 Prime Path （BFS）
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
题目大意：题目大概的意思就是给你两个素数找出从一个素数到另一个素数最少需要几步能实现，如果不能实现就输出Impossible，如果可以就输出步数，且实现的过程也就是变化的过程一定是要是素数才行。
思路：考虑bfs，首先对素数打表，这样我们就知道这个数是不是素数，但是也可以写一个判断函数，但是这样就会慢一些，其次便是广搜了，我们依次对每一位进行遍历，如果当前遍历的结果已经找到了那么直接return就行
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5 + 10;
int vis[maxn], prime[maxn], tot, step[maxn];
void judge() //素数打表，也可以写一个判断函数
{
for (int i = 1000; i < 10000; ++i)
{
for (int j = 2; j * j <= i; ++j)
{
int flag = 1;
if (i % j == 0)
{
prime[i] = 0;
flag = 0;
break;
}
if (flag)
prime[i] = 1;
}
}
}
int bfs(int x, int y)
{
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(vis));
queue<int> q;
q.push(x);
vis[x] = 1;
int a[10];
while (!q.empty())
{
int xx = q.front();
q.pop();
if (xx == y) //如果找到了就返回，这个代码一定要写在while循环里面，因为是遍历查找
return step[xx];
a[0] = xx % 10; //个位
a[1] = xx / 10 % 10; //十位
a[2] = xx / 100 % 10; //百位
a[3] = xx / 1000; //千位
for (int i = 0; i < 4; ++i) //依次遍历每一位
{
int num = a[i]; //临时储存，防止后序的干扰
for (int j = 0; j < 10; ++j) //每一位有10种变化
{
if (j != num) //数字不能是本身不然就没有意义了
{
a[i] = j; //赋值
int cnt = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000; //重新得到的数
if (!vis[cnt] && prime[cnt]) //判断是否满足题目的要求
{
step[cnt] = step[xx] + 1;
vis[cnt] = 1;
q.push(cnt);
}
}
}
a[i] = num; //让之前的数保持不变
}
}
return -1;
}
int main()
{
int n;
judge();
scanf("%d", &n);
while (n--)
{
int x, y;
scanf("%d%d", &x, &y);
if (bfs(x, y) == -1)
puts("Impossible");
else
printf("%d\n", bfs(x, y));
}
}
还有另外一种，思路差不多，但是较为复杂。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#define lowbit(x) x &(-x)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000
using namespace std;
const double pi = acos(-1.0);
const int maxn = 1e5;
const double eps = 1e-8;
int t;
int n, m;
int flag;
bool vis[10010];
int check[maxn + 10];
void init()
{
memset(vis, true, sizeof(vis));
vis[1] = false;
for (int i = 2; i <= maxn; i++)
for (int j = i * 2; j <= maxn; j += i)
vis[j] = false;
return;
}
struct node
{
int x;
int step;
node(int xx, int s)
{
x = xx;
step = s;
}
};
void bfs(int num, int step)
{
check[num] = 1;
queue<node> q;
q.push(node(num, step));
while (!q.empty())
{
node now = q.front();
q.pop();
if (now.x == m)
{
printf("%d\n", now.step);
flag = 1;
return;
}
for (int i = 0; i <= 9; i++)
{
//个位
int fx = (now.x / 10) * 10 + i;
if (check[fx] == 0 && vis[fx] == true)
{
q.push(node(fx, now.step + 1));
check[fx] = 1;
}
}
for (int i = 0; i <= 9; i++)
{
//十位
int fx = (now.x / 100) * 100 + i * 10 + now.x % 10;
if (check[fx] == 0 && vis[fx] == true)
{
q.push(node(fx, now.step + 1));
check[fx] = 1;
}
}
for (int i = 0; i <= 9; i++)
{
//百位
int fx = (now.x / 1000) * 1000 + i * 100 + now.x % 100;
if (check[fx] == 0 && vis[fx] == true)
{
q.push(node(fx, now.step + 1));
check[fx] = 1;
}
}
for (int i = 1; i <= 9; i++)
{
//千位
int fx = i * 1000 + now.x % 1000;
if (check[fx] == 0 && vis[fx] == true)
{
q.push(node(fx, now.step + 1));
check[fx] = 1;
}
}
}
return;
}
int main()
{
init();
scanf("%d", &t);
while (t--)
{
flag = 0;
memset(check, 0, sizeof(check));
scanf("%d%d", &n, &m);
bfs(n, 0);
if (flag == 0)
printf("Impossible\n");
}
return 0;
}
| 与其做着不可能实现的梦，不如乘早醒来做自己该做的事，凭空妄想只会蹉跎岁月，脚踏实地方至星辰大海 |
|---|
