首页 > 代码库 > POJ - 3126 - Prime Path
POJ - 3126 - Prime Path
题目链接：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; }
POJ - 3126 - Prime Path
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。