#include <iostream>
#include <queue>
#include <math.h>

using namespace std;
int isprime(int m)
{
	for(int i = 2; i*i <= m; i++)
		if(m % i == 0) return 0;
	return 1;
 } 
void BFS(int n,int k)
{
	int vis[10005] = {0};
	int step[10005];
	queue <int> q;
	int head,end;
	q.push(n);
	vis[n] = 1;
	step[n] = 0;
	while(!q.empty()){
		head = q.front();
		q.pop();
		for(int i = 0; i < 4; ++i){
			for(int j = 0; j <= 9; ++j){ //一开始本人 写成了 i<9 结果又重写了另一个算法 然后发现我这错了 我擦 傻了  
				if(i == 3 && j == 0) continue;
				if(i == 0 ) end = (head/10)*10 + j;
				else if(i == 1 ) end = (head/100)*100+head%10+j*10;
				else if(i == 2 ) end = (head/1000)*1000+head%100+j*10*10;
				else if(i == 3 ) end = head%1000 + j*1000;
				int max = k/1000;
				if(!vis[end] && isprime(end)){ //原本想加end1000<max来剪枝的，然后又debug半天发现不能 服了 
					q.push(end);
					vis[end] = 1;
					step[end] = step[head] + 1;
					if(end == k){
						cout << step[end] << endl;
						return;
					}
				}
			}
		}
	}
	cout << "Impossible\n"; //我还忘了有impossible 然后又。 服了服了 
}
int main()
{
	int T;cin >> T;
	while(T--){
		int n,k;
		cin >> n >> k;
		if(n == k) cout << 0 << endl;
		else BFS(n,k);
	}
}

• Re:经典BFS 本人写了半个小时代码 degug一上午 服了 犯了小学生错误 服了 (1309) 201801060731 2021-04-08 17:32:41
• Re:经典BFS 本人写了半个小时代码 degug一上午 服了 犯了小学生错误 服了 (1309) 2249619829 2022-01-23 11:07:37