关键词：
题目链接：https://vjudge.net/problem/POJ-3126
题目大意：有两个四位数门牌号，先要从第一个门牌号到达第二个门牌号，中间每次只能改变门牌号的其中一个数字，且只能经过素数，问最少
要经过多少次移动到达终点。
题目分析：简单的BFS，先素数打表然后进行BFS即可。
给出代码：
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <string> using namespace std; bool is_prime[10000+10]; int mark[10000+10]; int a,b; struct num { int x; int step; num(int xx=0,int steps=0) { x=xx; step=steps; } }; void init() { memset(is_prime,1,sizeof(is_prime)); is_prime[0]=0; is_prime[1]=0; for(int i=2;i<=10000;i++) { if(is_prime[i]) { for(int j=i+i;j<=10000;j+=i) { is_prime[j]=0; } } } } int bfs() { queue<num> q; q.push(num(a,0)); mark[a]=0; while(!q.empty()) { num c=q.front(); q.pop(); if(c.x==b) return c.step; else { int n=c.x; int a1=n/1000; n=n%1000; int a2=n/100; n=n%100; int a3=n/10; int a4=n%10; // cout<<a1*1000+a2*100+a3*10+a4<<endl; int h=c.x; for(int i=1;i<=9;i++) { int v=i*1000+a2*100+a3*10+a4; if(is_prime[v]&&v!=h&&mark[v]) { q.push(num(v,c.step+1)); mark[v]=0; } } for(int i=0;i<=9;i++) { int v=a1*1000+i*100+a3*10+a4; if(is_prime[v]&&v!=h&&mark[v]) { q.push(num(v,c.step+1)); mark[v]=0; } } for(int i=0;i<=9;i++) { int v=a1*1000+a2*100+i*10+a4; if(is_prime[v]&&v!=h&&mark[v]) { q.push(num(v,c.step+1)); mark[v]=0; } } for(int i=0;i<=9;i++) { int v=a1*1000+a2*100+a3*10+i; if(is_prime[v]&&v!=h&&mark[v]) { q.push(num(v,c.step+1)); mark[v]=0; } } } } return -1; } int main() { init(); int T; cin>>T; while(T--) { memset(mark,1,sizeof(mark)); //int a,b; cin>>a>>b; int t=bfs(); cout<<t<<endl; } return 0; }
poj3126primepath（搜索专题）
PrimePathTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 20237 Accepted: 11282DescriptionTheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecurityst 查看详情
poj-3126-primepath
题目链接：https://vjudge.net/problem/POJ-3126题目大意：有两个四位数门牌号，先要从第一个门牌号到达第二个门牌号，中间每次只能改变门牌号的其中一个数字，且只能经过素数，问最少 ... 查看详情
poj3126primepath（bfs+欧拉线性素数筛）
DescriptionTheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethefour-digitroomnumbersontheiroffices.—Itisamatterofsecuritytochangesuchthingseve 查看详情
kuangbin带你飞专题poj-3126primepath
原题重现：TheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethefour-digitroomnumbersontheiroffices.—Itisamatterofsecuritytochangesuchthingsev 查看详情
poj3126-primepath(bfs)
题目地址：id=3126">POJ3126题意：给你两个4位的都是素数正整数n,m，每次能够变个十百千位中的一个数（变化后也是素数，问最少经过多少次变化n能变成m，假设不能输出Impossible(窝认为并没有不成立的情况思路：每次变化一位，然... 查看详情
poj-3126primepath
TheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethefour-digitroomnumbersontheiroffices. —Itisamatterofsecuritytochangesuchthingseverynowandthen,tokeeptheenemyinthedark. —Butlook,Ihavechosenmynumber1033forgoodreasons.Iam... 查看详情
poj3126primepath(bfs+素数筛)
链接:Here!思路:素数表+BFS,对于每个数字来说,有四个替换位置,每个替换位置有10种方案(对于最高位只有9种),因此直接用BFS搜索目标状态即可.搜索的空间也不大.../*************************************************************************>FileName:E.c... 查看详情
poj3126primepath
题意：给两个四位数素数X，Y，每次可变换X的一位数字，变换后的数字应为素数，问X变为Y的最小变换次数。分析：宽度搜索，每次将所有满足条件的，改变X的某一位数的后的素数入队列。代码：1#include<iostream>2#include<cstd... 查看详情
poj3126primepath（素数路径）
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{fon 查看详情
poj-3126-primepath（bfs)(代码片段)
PrimePathPOJ-3126题意：给出两个四位素数a,b。然后从a开始，每次可以改变四位中的一位数字，变成c，c可以接着变，直到变成b为止。要求c必须是素数。求变换次数的最小值。（a,b,c都是四位数字，输入时没有前导零）分析：每次改... 查看详情
kuangbin带你飞专题poj-3126primepath
原题重现：TheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethefour-digitroomnumbersontheiroffices.—Itisamatterofsecuritytochangesuchthingseverynowandthen,tokeeptheenemyinthedark.—Butlook,Ihavechosenmynumber1033forgoodreasons.Iam... 查看详情
poj3126primepath从一个素数变为另一个素数的最少步数/bfs(代码片段)
PrimePathTimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:26475Accepted:14555DescriptionTheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethe 查看详情