題意：給兩個四位素數，從第一個素數變換到第二個素數最少需要變換多少次，每次只變換一個位置上的數字，第一位數字不能為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;}新聞熱點
疑難解答
