| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9982 | Accepted: 5724 |
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.
― It is a matter of security to change such things every now and then, to keep the enemy in the dark.
― But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
― I know, so therefZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcmUgeW91ciBuZXcgbnVtYmVyIDgxNzkgaXMgYWxzbyBhIHByaW1lLiBZb3Ugd2lsbCBqdXN0IGhhdmUgdG8gcGFzdGUgZm91ciBuZXcgZGlnaXRzIG92ZXIgdGhlIGZvdXIgb2xkIG9uZXMgb24geW91ciBvZmZpY2UgZG9vci4gPGJyPgqhqiBObywgaXShr3Mgbm90IHRoYXQgc2ltcGxlLiBTdXBwb3NlIHRoYXQgSSBjaGFuZ2UgdGhlIGZpcnN0IGRpZ2l0IHRvIGFuIDgsIHRoZW4gdGhlIG51bWJlciB3aWxsIHJlYWQgODAzMyB3aGljaCBpcyBub3QgYSBwcmltZSEgPGJyPgqhqiBJIHNlZSwgYmVpbmcgdGhlIHByaW1lIG1pbmlzdGVyIHlvdSBjYW5ub3Qgc3RhbmQgaGF2aW5nIGEgbm9uLXByaW1lIG51bWJlciBvbiB5b3VyIGRvb3IgZXZlbiBmb3IgYSBmZXcgc2Vjb25kcy4gPGJyPgqhqiBDb3JyZWN0ISBTbyBJIG11c3QgaW52ZW50IGEgc2NoZW1lIGZvciBnb2luZyBmcm9tIDEwMzMgdG8gODE3OSBieSBhIHBhdGggb2YgcHJpbWUgbnVtYmVycyB3aGVyZSBvbmx5IG9uZSBkaWdpdCBpcyBjaGFuZ2VkIGZyb20gb25lIHByaW1lIHRvIHRoZSBuZXh0IHByaW1lLiA8YnI+Cjxicj4KTm93LCB0aGUgbWluaXN0ZXIgb2YgZmluYW5jZSwgd2hvIGhhZCBiZWVuIGVhdmVzZHJvcHBpbmcsIGludGVydmVuZWQuIDxicj4KoaogTm8gdW5uZWNlc3NhcnkgZXhwZW5kaXR1cmUsIHBsZWFzZSEgSSBoYXBwZW4gdG8ga25vdyB0aGF0IHRoZSBwcmljZSBvZiBhIGRpZ2l0IGlzIG9uZSBwb3VuZC4gPGJyPgqhqiBIbW0sIGluIHRoYXQgY2FzZSBJIG5lZWQgYSBjb21wdXRlciBwcm9ncmFtIHRvIG1pbmltaXplIHRoZSBjb3N0LiBZb3UgZG9u"t know some very cheap software gurus, do you
― In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
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，每次变换时只能变一个数字，即变换后的数与变换前的数只有一个数字不同，并且要保证变换后的四位数也是素数。求最小的变换次数；如果不能完成变换，输出Impossible。
无论怎么变换，个位数字一定是奇数（个位数字为偶数肯定不是素数），这样枚举个位数字时只需枚举奇数就行；而且千位数字不能是0。所以可以用广搜，枚举各个数位上的数字，满足要求的数就加入队列，直到变换成功。因为是广搜，所以一定能保证次数最少。
AC代码：
#include有一点我不明白：上面的代码选G++可以AC，但是用C++就Compile Error。#include #include #include #include using namespace std; int n, m; const int N = 1e4 + 100; int vis[N]; struct node { int x, step; }; queue Q; bool judge_prime(int x) //判断素数 { if(x == 0 || x == 1) return false; else if(x == 2 || x == 3) return true; else { for(int i = 2; i <= (int)sqrt(x); i++) if(x % i == 0) return false; return true; } } void BFS() { int X, STEP, i; while(!Q.empty()) { node tmp; tmp = Q.front(); Q.pop(); X = tmp.x; STEP = tmp.step; if(X == m) { printf("%d\n",STEP); return ; } for(i = 1; i <= 9; i += 2) //个位 { int s = X / 10 * 10 + i; if(s != X && !vis[s] && judge_prime(s)) { vis[s] = 1; node temp; temp.x = s; temp.step = STEP + 1; Q.push(temp); } } for(i = 0; i <= 9; i++) //十位 { int s = X / 100 * 100 + i * 10 + X % 10; if(s != X && !vis[s] && judge_prime(s)) { vis[s] = 1; node temp; temp.x = s; temp.step = STEP + 1; Q.push(temp); } } for(i = 0; i <= 9; i++) //百位 { int s = X / 1000 * 1000 + i * 100 + X % 100; if(s != X && !vis[s] && judge_prime(s)) { vis[s] = 1; node temp; temp.x = s; temp.step = STEP + 1; Q.push(temp); } } for(i = 1; i <= 9; i++) //千位 { int s = i * 1000 + X % 1000; if(s != X && !vis[s] && judge_prime(s)) { vis[s] = 1; node temp; temp.x = s; temp.step = STEP + 1; Q.push(temp); } } } printf("Impossible\n"); return ; } int main() { int t, i; scanf("%d",&t); while(t--) { while(!Q.empty()) Q.pop(); scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); vis[n] = 1; node tmp; tmp.x = n; tmp.step = 0; Q.push(tmp); BFS(); } return 0; }