| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 14276 | Accepted: 8045 |
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
Output
Sample Input
3 1033 8179 1373 8017 1033 1033
Sample Output
6 7 0
Source
#include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<iostream> #include<algorithm> using namespace std; bool vis[10005]; struct node{ int x,step; }; node u,v; bool prime(int u){//judge是否为素数
for(int i=2;i*i<10000;i++) if(u%i==0) return false; return true; } int bfs(int start,int end){ u.x=start; u.step=0; queue<node>q; q.push(u); memset(vis,false,sizeof(vis)); vis[start]=true; while(!q.empty()){ u=q.front(); q.pop(); if(u.x==end) return u.step; for(int i=0;i<=3;i++){ double t1=pow((double)10,i);//pow函数中的10必须转化为double型，若不转化，则会出现以下问题
//当i为2的时候结果为99，当i为4的时候结果为9999，具体原因我也不太清楚，可能是由于
//C++中对pow函数的定义为pow（double，double），如果强加用int可能会有精度损失
int x=(u.x/(int)t1)%10; for(int j=0;j<=9;j++){ if(j==0&&i==3）//最高位不可以为0continue; int temp2=u.x+(j-x)*t1;//获得下一个数 if(prime(temp2)&&!vis[temp2]){//如果下一个数不为素数并且没有别访问过 vis[temp2]=true; v.step=u.step+1; v.x=temp2; q.push(v); } } } } return -1; } int main(){ int t; scanf("%d",&t); while(t--){ int start,end; scanf("%d%d",&start,&end); int ans=bfs(start,end); if(ans==-1) printf("Impossible\n"); else printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/13224ACMer/p/4741473.html