D2082O 【BFS例题】内阁会议

#include<bits/stdc++.h>

using namespace std;
char s[5],s2;
int n,t,ts,sm=0,a[10001]={};
struct node{
	int n,cnt;
};
void fs(int x){
	int u=x;
	s[0]=(u%10)+'0';
	u/=10;
	s[1]=(u%10)+'0';
	u/=10;
	s[2]=(u%10)+'0';
	u/=10;
	s[3]=(u%10)+'0';
	u/=10;
}
bool check(int n){
	if(n<1000 || n > 9999)return false;
	if(a[n] == 1)return false;
	for(int i = 2;i*i <= n;i++){
		if(n % i == 0){
			return false;
		}
	}
	return true;
}
void bfs(){
	queue<node> q;
	q.push((node){t,0});
	while(!q.empty()){
		node d=q.front();
		q.pop();
		int nt=d.n;
		fs(nt);
		if(nt ==ts){
			cout << d.cnt << endl;
			return ;
		}
		for(int j = 3;j >= 0;j--){
			for(int i = 0;i <= 9;i++){
				s2=s[j];
				s[j] = i+'0';
				int temp=s[0]-'0'+(s[1]-'0')*10+(s[2]-'0')*100+(s[3]-'0')*1000;
				if(check(temp)){
					//cout << temp << endl;
					q.push((node){temp,d.cnt+1});
					a[temp]=1;
				}
				s[j]=s2;
			}
		}
	}
	cout << "Impossible" << endl;
}
void init(){
	for(int i = 1;i <= 10001;i++){
		a[i]=0;
	}
}
signed main(){
	cin >> n;
	
	for(int i = 1;i <= n;i++){
		cin >> t >> ts;
		init();
		bfs();
	}
	return 0;
}
/*
1
1033 8179
*/