万恶的VC6.0,头文件没写竟然也不报错,让我得到两个CompileError……
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6196 | Accepted: 3535 |
Description
— 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 therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don'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.
1033
1733
3733
3739
3779
8779
8179
The 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.
Input
Output
Sample Input
3 1033 8179 1373 8017 1033 1033
Sample Output
6 7 0
#include<iostream> #include<cstring> #include<cmath> using namespace std; int not_prime[10000]={0}; int queue[10000]={0}; int step[10000]={0}; int visited[10000]={0}; int d[5];//d[i]存第i位数字 int BFS(int num1, int num2) { int i, j; int number; int temp; int m; int front=0, rear=1; queue[front]=num1; visited[num1]=1;//访问过了 while( front!=rear) { temp=queue[front]; front++; for( j=1; j<=4; j++)//改变第j位数字 { m=pow(10, 4-j); d[j]=temp/m%10;//得到第j位上的数字 i=(j==1)?1:0;//如果改变第一位数字,则数字从1开始取,其他从0开始 while( i<=9 ) { if(j==4 &&(i%2==0||i%5==0))//剪枝 { i++; continue; } number=temp+(i-d[j])*m; if( number==num2)//搜索到,结束 return step[temp]+1; if( !visited[number] && !not_prime[number])//若未访问过,且为素数 { queue[rear]=number; visited[number]=1; step[number]=step[temp]+1; rear++; } i++; } } } return 0; } int main() { int n; int num1, num2; int i, j; for(i=2; i<10000; i++)//判断不是素数就赋值为1 for(j=2; i*j<10000; j++) not_prime[i*j]=1; cin>>n; while( n--) { memset(visited, 0, sizeof(visited)); memset(step, 0, sizeof(step)); cin>>num1>>num2; if( num1== num2 ) cout<<0<<endl; else cout<<BFS(num1, num2)<<endl; } }