做司法考试题目的网站,牛商网招聘,网站导航结构设计,宜昌百度网站建设题目#xff1a;
孤单的zydsg又一次孤单的度过了520#xff0c;不过下一次不会再这样了。zydsg要做些改变#xff0c;他想去和素数小姐姐约会。 所有的路口都被标号为了一个4位素数#xff0c;zydsg现在的位置和素数小姐姐的家也是这样#xff0c;如果两个路口间只差1个数…题目
孤单的zydsg又一次孤单的度过了520不过下一次不会再这样了。zydsg要做些改变他想去和素数小姐姐约会。 所有的路口都被标号为了一个4位素数zydsg现在的位置和素数小姐姐的家也是这样如果两个路口间只差1个数字则有一条路连通两个路口。例如1033和1073间有一条路连接 现在你知道了zydsg的位置和素数小姐姐的家问最少zydsg要走多少条路才能见到素数小姐姐。例如如果zydsg在1033素数小姐姐的家在8179最少要走6条街走法为 1033 1733 3733 3739 3779 8779 8179 Input 输入数据有多组首先是一个数字n代表之后有n组数据。 其次在每一组输入中都包含两个数字a和b代表zydsg的位置和素数小姐姐家的位置。 其中a和b都是四位数而且不含前导0。 Output 每组输入输出一行表示zydsg最少需要走多少条路。若不存在合法的路径则输出单词“Impossible”。 Sample Input 3 1033 8179 1373 8017 1033 1033 Sample Output 6 7 0
分析与解答
水题一个 结点 改个位十位百位千位最终到达要求的答案仍然是层次遍历把各个位的数都变一遍存到队列里然后一层存完拿出队首再往里面存直到队首刚好是答案那就输出并return。 注意这个是多实例也就是说需要多个queue所以每次bfs之前注意把前面的queue清空这题我是把queue定义到外面了如果定义到bfs里面就不用再清空queue了 代码参考 https://blog.csdn.net/LYHVOYAGE/article/details/18228531
#includecstdio
#includecstring
#includecmath
#includequeue
#includealgorithm
using namespace std;int n, m;
const int N 1e4 100;
int vis[N];
struct node
{int x, step;
};
queuenode Q;int prime[10001];
int pri(int k){for(int i2;i*ik;i){if(k%i0) return 0;}return 1;
}void abd(){memset(prime,0,sizeof(prime));for(int i1000;i9999;i){if(pri(i)) prime[i]1;}
}void BFS(int n)
{node tmp;tmp.x n;tmp.step 0;Q.push(tmp);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] 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] 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] 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] 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);abd();while(t--){while(!Q.empty()) Q.pop();scanf(%d%d,n,m);memset(vis,0,sizeof(vis));vis[n] 1;BFS(n);}return 0;
}
