注意千位的时候要从1开始
#include <algorithm> #include <iostream> #include <stdio.h> #include <queue> #include <string.h> #include <math.h> using namespace std; struct node { int x; int step; }; int book[10000]; int n, m; bool judge(int x) { // for(int i = 2;i <= sqrt(x);i++){ // if(x%i==0) // return false; // } // return true; int i; if(x==1||x==0||x==2) return 0; else { for(i=2;i<=sqrt(x);i++) { if(x%i==0) return 0; } return 1; } } int BFS() { node a, ans; queue<node>Q; ans.x = n; ans.step = 0; Q.push(ans); book[n] = 1; int x, i; while(!Q.empty()){ a = Q.front(); Q.pop(); if(a.x == m){ return a.step; } for(i = 0;i < 10;i++){//个位 x = a.x/10*10+i; if(judge(x)&&!book[x]){ ans.step = a.step+1; ans.x = x; book[x] = 1; Q.push(ans); } } for(i = 0;i < 10;i++){//十位 x = a.x/100*100+i*10+a.x%10; if(judge(x)&&!book[x]){ ans.step = a.step+1; ans.x = x; book[x] = 1; Q.push(ans); } } for(i = 0;i < 10;i++){//百位 x = a.x/1000*1000+i*100+a.x%100; if(judge(x)&&!book[x]){ ans.step = a.step+1; ans.x = x; book[x] = 1; Q.push(ans); } } for(i = 1;i < 10;i++){//千位 x = i*1000+a.x%1000; if(judge(x)&&!book[x]){ ans.step = a.step+1; ans.x = x; book[x] = 1; Q.push(ans); } } } return -1; } int main() { int t; scanf("%d", &t); while(t--){ memset(book,0,sizeof(book)); scanf("%d %d", &n, &m); int ans = BFS(); if(ans==-1){ printf("Impossible\n"); }else { printf("%d\n", ans); } } return 0; }