加粗样式## 题目链接: [Prime Path]
大致题意:
T组，每组给出两个四位素数a，b，a每次可以改变某一位的数字，但满足改变后的数字也是素数，问最少变化几次使a变为b
解题思路:
问最少的变化，所以选bfs，防止不超时，开一个数组记录1所有的素数，然后对每一位数字进行遍历即可
AC代码:
#include <iostream>
#include<cmath>
#include <queue>
using namespace std
;
int prime
[10010], a
[10010], c
[4];
int fact(int n
) {
int t
= sqrt((double)n
);
for (int i
= 2; i
<= t
; i
++) {
if (n
% i
== 0)
return 0;
}
return -1;
}
void bfs(int x
, int y
) {
int t
, tmp
;
a
[x
] = 0;
queue
<int> q
;
q
.push(x
);
while (!q
.empty()) {
t
= q
.front(); q
.pop();
tmp
= t
;
if (a
[y
] != -1) {
cout
<< a
[y
] << endl
; return;
}
for (int i
= 0; i
< 4; i
++) {
c
[i
] = tmp
% 10; tmp
/= 10;
}
for (int i
= 0; i
<= 9; i
++) {
tmp
= i
+ 10 * c
[1] + 100 * c
[2] + 1000 * c
[3];
if (a
[tmp
] == -1) {
a
[tmp
] = a
[t
] + 1; q
.push(tmp
);
}
}
for (int i
= 0; i
<= 9; i
++) {
tmp
= c
[0] + 10 * i
+ 100 * c
[2] + 1000 * c
[3];
if (a
[tmp
] == -1) {
a
[tmp
] = a
[t
] + 1; q
.push(tmp
);
}
}
for (int i
= 0; i
<= 9; i
++) {
tmp
= c
[0] + 10 * c
[1] + 100 * i
+ 1000 * c
[3];
if (a
[tmp
] == -1) {
a
[tmp
] = a
[t
] + 1; q
.push(tmp
);
}
}
for (int i
= 1; i
<= 9; i
++) {
tmp
= c
[0] + 10 * c
[1] + 100 * c
[2] + 1000 * i
;
if (a
[tmp
] == -1) {
a
[tmp
] = a
[t
] + 1; q
.push(tmp
);
}
}
}
cout
<< "Impossible\n";
}
int main(void)
{
for (int i
= 2; i
< 10010; i
++)prime
[i
] = fact(i
);
int t
; cin
>> t
;
while (t
--) {
int x
, y
; cin
>> x
>> y
;
memcpy(a
, prime
, 10010 * sizeof(int));
bfs(x
, y
);
}
return 0;
}
END
