一篇意义不明的代码保存+题解
2025-06-04 19:46:58
发布于：上海
8阅读
0回复
0点赞
本代码解决"四位数素数路径"问题，即找出两个4位素数间每次只改变一位数字的最短转换路径。采用以下策略：
预处理阶段：使用筛法生成所有4位素数，并为每个素数构建邻接表，存储所有可通过单次数字变换得到的其他素数
查询阶段：使用BFS算法搜索最短路径，利用队列实现层级遍历，确保首次到达终点时的路径长度即为最短。
#include<bits/stdc++.h>
using namespace std;
/* 全局数据结构说明：
isPrime - 标记是否为素数
vis - BFS访问标记数组
mp - 记录到起点的最短距离
Map - 邻接表，存储每个数的可达素数 */
bool isPrime[10000],vis[10000]={0};
int mp[10000];
vector<int> Map[10000];
/* 初始化函数：
1. 使用筛法生成素数表
2. 为每个素数构建邻接表 */
void init(){
// 筛法初始化（注意：这里isPrime需要全初始化为true）
memset(isPrime,1,sizeof(isPrime));
isPrime[0]=isPrime[1]=0; // 处理0和1的特殊情况
// 标准埃拉托斯特尼筛法实现
for(int i=2;i<=9999;i++)
if(isPrime[i])
for(int j=i*2;j<=9999;j+=i)
isPrime[j]=0;
// 邻接表构建：遍历所有4位素数
for(int i=1000;i<=9999;i++){
if(!isPrime[i]) continue; // 跳过非素数
// 分解数字的各位数字：d[0]为千位，d[3]为个位
int d[4],num=i;
d[0]=num/1000; num%=1000;
d[1]=num/100; num%=100;
d[2]=num/10; num%=10;
d[3]=num;
// 生成所有可能的一位数字变化
for(int j=0;j<4;j++){
int a=d[j];
for(int digit=0;digit<=9;digit++){
// 跳过相同数字和首位变0的情况
if(digit==a||(j==0&&digit==0)) continue;
// 构造新数字：替换第j位为digit
int new_num=0;
for(int k=0;k<4;k++){
if(k==j) new_num=new_num*10+digit;
else new_num=new_num*10+d[k];
}
// 如果是有效素数则加入邻接表
if(new_num>=1000&&new_num<=9999&&isPrime[new_num])
Map[i].push_back(new_num);
}
}
}
}
/* BFS搜索最短路径：
s - 起点素数
e - 终点素数
返回值：最短变换步数 */
int bfs(int s,int e){
if(s==e) return 0; // 起点终点相同
// 初始化访问状态和距离记录
for(int i=1000;i<=9999;i++){
vis[i]=0;
mp[i]=-1;
}
// BFS标准实现
queue<int> q;
q.push(s);
vis[s]=1;
mp[s]=0;
while(!q.empty()){
int f=q.front();
q.pop();
// 遍历所有邻接素数
for(int i=0;i<Map[f].size();i++){
if(!vis[Map[f][i]]){
vis[Map[f][i]]=1;
mp[Map[f][i]]=mp[f]+1; // 距离递增
if(Map[f][i]==e) // 找到终点
return mp[Map[f][i]];
q.push(Map[f][i]); // 加入队列
}
}
}
return 0; // 无通路时返回0
}
int main(){
init(); // 初始化素数表和邻接表
int t;
cin>>t;
while(t--){
int q,w;
cin>>q>>w;
cout<<bfs(q,w)<<endl; // 处理每个查询
}
return 0;
}
这里空空如也
有帮助，赞一个