第12课-单元测评(五)编程题T2

}͆‮

2025-11-14 20:40:07

发布于：浙江

6阅读

0回复

0点赞

端脑
题目描述
涛涛是一个计算爱好者，他十分热衷于研究各种数字游戏。并扬言，这世间就没有我涛某人解决不了的数字问题。
于是，在一个月黑风高的晚上，他被打晕拖上了面包车……
当他醒来的时候，发现自己处在一个巨大的广场内，这个广场的每一块地板上都有一个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;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

}͆‮
又盗我的

2025-11-14 来自浙江
0

全部评论 1

热门讨论