3126.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3126  User Id:fzk 
Memory:80K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>

int s[10000];
bool sign[10000];
int q[10000];
void init( ) {
	int i, j;
	for( i=2; i<10000; i++ )
		if( !s[i] ) {
			for( j=(i<<1); j<10000; j+=i )
				s[j] = true;
		}
}

int main( ) {
	int qh, qt, i, t, a, b, count, k, temp;

	scanf( "%d", &t );
	init( );

	while( t-- ) {
		scanf( "%d%d", &a, &b );
		memset( sign, 0, sizeof sign );
		qh = qt = 0;
		q[qt++] = a;
		sign[a] = true;
		q[qt++] = -1;
		count = 0;

		while( qh < qt ) {
			a = q[qh++];
			if( a == -1 ) {
				count++;
				q[qt++] = a;
				continue;
			}

			if( a == b )
				break;

			for( i=1; i<=1000; i*=10 ) {
				k = a%(i*10)/i;
				temp = a;
				while( k-- ) {
					temp -= i;
					if( temp>=1000 && !s[temp] && !sign[temp] ) {
						q[qt++] = temp;
						sign[temp] = true;
					}
				}

				k = a%(i*10)/i;
				temp = a;
				while( k++ < 9 ) {
					temp += i;
					if( !s[temp] && !sign[temp] ) {
						q[qt++] = temp;
						sign[temp] = true;
					}
				}
			}
		}
		if( qh == qt )
			printf( "Impossible\n" );
		else
			printf( "%d\n", count );
	}
	return 0;
}