# 【搜索】 Prime Path

```#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

int n, m;
const int N = 1e4 + 100;
int vis[N];
struct node
{
int x, step;
};
queue<node> Q;

bool judge_prime(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;
}
}

void BFS()
{
int X, STEP, i;
while(!Q.empty())
{
node tmp;
tmp = Q.front();
Q.pop();
X = tmp.x;
STEP = tmp.step;
if(X == m)
{
printf("%d\n",STEP);
return ;
}
for(i = 1; i <= 9; i += 2) //个位
{
int s = X / 10 * 10 + i;
if(s != X && !vis[s] && judge_prime(s))
{
vis[s] = 1;
node temp;
temp.x = s;
temp.step = STEP + 1;
Q.push(temp);
}
}
for(i = 0; i <= 9; i++) //十位
{
int s = X / 100 * 100 + i * 10 + X % 10;
if(s != X && !vis[s] && judge_prime(s))
{
vis[s] = 1;
node temp;
temp.x = s;
temp.step = STEP + 1;
Q.push(temp);
}
}
for(i = 0; i <= 9; i++) //百位
{
int s = X / 1000 * 1000 + i * 100 + X % 100;
if(s != X && !vis[s] && judge_prime(s))
{
vis[s] = 1;
node temp;
temp.x = s;
temp.step = STEP + 1;
Q.push(temp);
}
}
for(i = 1; i <= 9; i++) //千位
{
int s = i * 1000 + X % 1000;
if(s != X && !vis[s] && judge_prime(s))
{
vis[s] = 1;
node temp;
temp.x = s;
temp.step = STEP + 1;
Q.push(temp);
}
}
}
printf("Impossible\n");
return ;
}

int main()
{
int t, i;
scanf("%d",&t);
while(t--)
{
while(!Q.empty()) Q.pop();
scanf("%d%d",&n,&m);
memset(vis,0,sizeof(vis));
vis[n] = 1;
node tmp;
tmp.x = n;
tmp.step = 0;
Q.push(tmp);
BFS();
}
return 0;
}
```

## Prime Path （poj 3126 bfs）

Language: Default Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11703   Accepted: 6640 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to c

## F - Prime Path POJ 3126 筛选素数+bfs

F - Prime Path Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 3126 Description The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have t

## (简单) 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

## 双向广搜 POJ 3126 Prime Path

POJ 3126  Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 16204   Accepted: 9153 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 th

## poj 3126 Prime Path (bfs)

Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13813   Accepted: 7796 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-dig

## POJ 3126 Prime Path（BFS）

Prime Path Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12060   Accepted: 6843 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-dig

## Prime Path bfs搞定

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

## POJ 3126 Prime Path（素数路径）

p.MsoNormal { margin-bottom: 10.0000pt; font-family: Tahoma; font-size: 11.0000pt } h1 { margin-top: 5.0000pt; margin-bottom: 5.0000pt; text-align: left; font-family: 宋体; font-weight: bold; font-size: 24.0000pt } span.10 { font-family: "Times New Rom