端脑
题目描述
涛涛是一个计算爱好者,他十分热衷于研究各种数字游戏。并扬言,这世间就没有我涛某人解决不了的数字问题。
于是,在一个月黑风高的晚上,他被打晕拖上了面包车……
当他醒来的时候,发现自己处在一个巨大的广场内,这个广场的每一块地板上都有一个4位数的编号。突然广场上
的喇叭响起了声音:"欢迎来到端脑,你是前来挑战的第 79834817 名选手,你和前面的每一位选手一样都十分的聪明,
但是他们都没能从这关活着出去。如你所见,广场的每一个地板上都有一个 4 位数的编号,你现在所处的地板编号为 Q,
是一个素数,出口的编号为 W,也是一个素数,想要通关,很明显,你需要走到出口 W,但是你的移动,需要遵循一定
的规律。你每次移动后的地板,只能有一位数字进行改变,并且这个地板编号也得是一个素数,只有经过最少次数的
移动到达出口 W,才能通过这一关,祝你好运……"出于人道主义,请你帮助涛涛计算出从当前地板编号 Q 到达出口
地板编号 W,最少的移动次数是多少?
提示
0<t<=100,1000<=Q,W<=9999,变换过程中的数也是在 1000∼9999 之间
输入格式
第一行一个整数 t,表示测试数据组数
接下来 t 行,每行两个整数 Q,W
输出格式
t 行,每行一个数字表示答案,如果无法做到或不需要操作,请输出 0
算法分析:
从 Q 到 W 最少需要的步数,可以考虑广搜。广搜的每一步都是去选择四位数当中的某一位进行改变,同时又需要改变之后的数是素数。如果在广搜的过程中判断素数,那时间复杂度会很高,因此可以先预处理出每个数是不是素数(这里用的是埃氏筛,当然用 nsqrt(n) 的算法时间也是允许的)。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
bool prime[maxn];
int vis[maxn]; //vis[i]表示从Q到i需要的次数
void init() { //埃氏筛素数
prime[1] = 1;
for (int i = 2; i < maxn; i++) {
for (int j = 2 * i; j < maxn; j += i) prime[j] = 1;
}
}
int bfs(int Q, int W) {
memset(vis, -1, sizeof(vis)); //用-1表示从Q到不能到i,多组数据,每次需要初始化
queue<int> q;
q.push(Q);
vis[Q] = 0; //Q到Q的次数是0
while (q.size()) {
int r = q.front();
q.pop();
if (r == W) return vis[W];
for (int i = 0; i < 10; i++) {
//个位
int tm = r - r % 10 + i;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { //题目说改变后的数要在1000~9999范围内
q.push(tm);
vis[tm] = vis[r] + 1;
}
//十位
tm = r - (r / 10 % 10) * 10 + i * 10;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
//百位
tm = r - (r / 100 % 10) * 100 + i * 100;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
//千位
tm = r - (r / 1000 % 10) * 1000 + i * 1000;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
}
}
return 0;
}
int main() {
init();
int _;
cin >> ;
while (--) {
int Q, W;
cin >> Q >> W;
cout << bfs(Q, W) << '\n';
}
return 0;
}