poj 3126 Prime Path（bfs）

2019-11-08 02:52:10

字体：大中小

来源：转载

供稿：网友

题意：给两个四位素数，从第一个素数变换到第二个素数最少需要变换多少次，每次只变换一个位置上的数字，第一位数字不能为0

简单bfs

#include <cstdio>#include <cstring>#include <queue>using std::queue;struct node{ int val; int step;};bool PRime[10000];bool book[10000];int s,e,res;int num[4];void getPrime(){ memset(prime,0,sizeof(prime)); prime[0] = prime[1] = true; for(int i = 2; i < 10000; ++i) { if(!prime[i]) for(int j = 2*i; j < 10000; j += i) prime[j] = true;//false表示是素数，true表示不是素数 }}bool isPrime(int num){ return !prime[num];}void BFS(){ memset(book,0,sizeof(book)); queue<node> que; node head; head.val = s; head.step = 0; book[s] = true; que.push(head); int temp; while(!que.empty()) { node cur = que.front(); que.pop(); if(cur.val == e) { res = cur.step; return; } num[0] = cur.val/1000; num[1] = (cur.val/100)%10; num[2] = (cur.val/10)%10; num[3] = cur.val%10; for(int i = 0; i < 4; ++i) { temp = num[i]; for(int j = 0; j < 10; ++j) { if(i == 0 && j == 0) continue; if(temp != j) { num[i] = j; int n = num[0]*1000+num[1]*100+num[2]*10+num[3]; if(!book[n] && isPrime(n)) { node atp; atp.val = n; atp.step = cur.step + 1; book[n] = true; que.push(atp); } } } num[i] = temp; } }}int main(){ int t; getPrime(); scanf("%d",&t); while(t--) { res = -1; scanf("%d %d",&s,&e); BFS(); if(res == -1) printf("Impossible/n"); else printf("%d/n",res); } return 0;}

上一篇：程序开发路线图

下一篇：LeetCode 39. Combination Sum