POJ 3126 Prime Path(bfs)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 10000;
struct Node{
	int num,step;
}Now,Next;
int vis[MAXN];
int s,e,n;
bool Prime[MAXN];

void prime(){             // 将素数记录下来
	int m = sqrt(MAXN);
	memset(Prime,true,sizeof(Prime));
	Prime[0] = Prime[1] = false;
	for(int i=2;i<m;i++){
		if(Prime[i]){
			for(int j=i*i;j<MAXN;j+=i){
				Prime[j] = false;
			}
		}
	}
}

bool judge(int a,int b){       //判断是否只改变了一个数字
	int ans = 0;
	if(a % 10 != b % 10) ans++;
	if(a / 10 % 10 != b / 10 % 10) ans++;
	if(a / 100 % 10 != b / 100 % 10) ans++;
	if(a / 1000 != b / 1000) ans++;
	if(ans == 1) return true;
	else return false;
}

int bfs(){
	queue<Node> q;
	memset(vis,0,sizeof(vis));
	Now.num = s;
	Now.step = 0;
	vis[s] = 1;
	q.push(Now);
	while(!q.empty()){
		Now = q.front();
		q.pop();
		if(Now.num == e){
			return Now.step;
		}
		for(int i=1000;i<10000;i++){
			if(Prime[i] && judge(i,Now.num) && vis[i] == 0){
				vis[i] = 1;
				Next.num = i;
				Next.step = Now.step + 1;
				q.push(Next);
			}
		}
	}
	return -1;
}
int main()
{
	prime();
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&s,&e);
		int temp = bfs();
		if(temp != -1){
			printf("%d\n",temp);
		}
		else {
			printf("Impossible\n");
		}
	}
	return 0;
}
/*
  [来源] POJ 3126
	[题目] Prime Path
	[题意]
	   给出a，b两个四位数字，a一次只能改变一个数字，求最少需要改变几次才能变成b，而且每次改变
		 一个数字后这个数也应是素数(BFS)。
	[输入]
	   3
	   1033 8179
       	   1373 8017
	   1033 1033
        [输出]
           6
	   7
	   0
*/