1973.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1973
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
const int MAX = 10000;
bool prime[MAX];
bool vis[MAX];
void cal_prime() {
	int i,j;
	for (i=3;i<=MAX;i+=2) {
		if (!prime[i]) {
			for (j=i+i;j<=MAX;j+=i) prime[j] = true;
		}
	}
}
int s,t,ans;
int dig[4];
queue<int> sq;
void bfs() {
	int i,j,k,now,tmp,next;
	ans = 0;
	sq.push(s);
	vis[s] = true;
	while (!sq.empty()) {
		int l = sq.size();
		while (l --) {
			now = sq.front();
			sq.pop();
			if (now == t) return;
			for (i=0;i<4;i++,now/=10) dig[i] = now % 10;
			for (i=0;i<4;i++) {
				tmp = dig[i];
				for (j=0;j<=9;j++) {
					if (i==3 && j==0) continue;
					dig[i] = j;
					for (k=next=0;k<4;k++) next = next*10 + dig[3-k]; 
					if ((next|1) && !prime[next] && !vis[next]) {
						vis[next] = true;
						sq.push(next);
					}
				}
				dig[i] = tmp;
			}
		}
		ans ++;
	}
}
int main() {
	int i,j,cas;
	cal_prime();
	scanf("%d",&cas);
	while (cas --) {
		scanf("%d %d",&s,&t);
		while (!sq.empty()) sq.pop();
		memset(vis,0,sizeof(vis));
		bfs();
		printf("%d\n",ans);
	}
}