Description
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.1033The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
1733
3733
3739
3779
8779
8179
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.Sample Input
3 1033 8179 1373 8017 1033 1033
Sample Output
6 7 0 意解:題目給出兩個素數n,m,問是否可以從n變為m; 直接對每一個位BFS; AC代碼:#include #include#include #include #include using namespace std; typedef long long ll; const int M = 10000; int check[M],prime[M],tot,ny,Min; bool vis; bool map[10000];//標記已經BFS過的; int n,m,T; /**********/ struct Node //存儲每個數和到達該數的時間 { int x,t; }; void make_prime() //把四位數的素數存儲進prime數組 { tot = 0; for(int i = 2; i < M; i++) { if(!check[i]) { if(i > 1000) prime[tot++] = i; for(int j = i + i; j < M; j += i) check[j] = 1; } } } void bfs() { Node tp; tp.x = n; tp.t = 0; map[n] = true; queue ms; ms.push(tp); while(!ms.empty()) { tp = ms.front(); ms.pop(); int d[4],i = 0,t = tp.x; while(t) { d[i++] = t % 10; t /= 10; } for(i = 0; i < 4; i++) { for(int j = 0; j <= 9; j++) { if(j == d[i]) continue; if(i == 0 && (j % 2 == 0 || j == 5)) continue; //本身不是素數的,直接退出 if(i == 3 && j == 0) continue;//首位不能為0 int u = 3,sum = 0; while(u != -1) { if(u == i) { sum = sum * 10 + j; } else sum = sum * 10 + d[u]; u--; } if(check[sum] || map[sum]) continue;//合數或者已被標記過的,直接退出 Node c; map[sum] = true; c.x = sum; c.t = tp.t + 1; if(sum == m) { vis = 1; printf("%d\n",c.t); return; } ms.push(c); } } } } int main() { make_prime(); scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); memset(map,false,sizeof(map)); if(n == m) puts("0"); else { vis = 0; bfs(); if(!vis) puts("Impossible"); } } return 0; }