#include<iostream>
#include<string>
#include<cmath>
using namespace std;

bool isprime(int a)
{
	int i;
	for(i = 2; ; i ++) 
		if(a % i == 0)
			break;
	if(i <= sqrt(float(a)))
		return false;
	return true;
}


int main()
{
	//freopen("in2.txt", "r", stdin);
	int rear, front, temp, next;
	int step[10000], que[10000];
	int begin, end;
	int N, j;

	cin >> N;
	while(N --) {
		cin >> begin >> end;
		memset(step, -1, sizeof(step));
		memset(que, 0, sizeof(que));
		front = rear = 0;
		step[begin] = 0;
		que[rear ++] = begin;
		while(front < rear) {
			temp = que[front ++];
			if(temp == end) break;
			for(j = 1; j < 10; j ++) {
				next = temp + j;
				if(isprime(next) == true && next <= 9999 && step[next] == -1 
					&& (next / 10) % 10 == (temp / 10) % 10) {             //第2位相等
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
				next = temp - j;
				if(isprime(next) == true && next >= 1000 && step[next] == -1 
					&& (next / 10) % 10 == (temp / 10) % 10) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
			}
			if(next == end) break;
			for(j = 10; j < 100; j = j + 10) {
				next = temp + j;
				if(isprime(next) == true && next <= 9999 && step[next] == -1  
					&& (next / 100) % 10 == (temp / 100) % 10) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
				next = temp - j;
				if(isprime(next) == true && next >= 1000 && step[next] == -1  
					&& (next / 100) % 10 == (temp / 100) % 10) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
			}
			if(next == end) break;
			for(j = 100; j < 1000; j = j + 100) {
				next = temp + j;
				if(isprime(next) == true && next <= 9999 && step[next] == -1 
					&& next /1000 == temp / 1000 ) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
				next = temp - j;
				if(isprime(next) == true && next >= 1000 && step[next] == -1 
					&& next /1000 == temp / 1000 ) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
			}
			if(next == end) break;
			for(j = 1000; j < 10000; j = j + 1000) {
				next = temp + j;
				if(isprime(next) == true && next <= 9999 && step[next] == -1 
					&& (next /100) % 10 == (temp / 100) % 10
					&& (next / 10) % 10 == (temp / 10) % 10
					&& next % 10 == temp % 10) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
				next = temp - j;
				if(isprime(next) == true && next >= 1000 && step[next] == -1 
					&& (next /100) % 10 == (temp / 100) % 10
					&& (next / 10) % 10 == (temp / 10) % 10
					&& next % 10 == temp % 10) {
					step[next] = step[temp] + 1;
					if(next == end) break;
					que[rear ++] = next;
					//cout << next << endl;
				}
			}
			if(next == end) break;
		}
		cout << step[end] << endl;
	}
	return 0;
}

• Re:我的广搜啊！！！！！！！！！！！为什么不行！！！！！！！！！ (19) __24__ 2010-07-26 15:19:46