POJ_3126_(BFS)

POJ 3126

• 先把所有1000~10000素数排出来
• 改变给出起点数a的4位,每一位9种选择(1,2,3...9),
• bfs,求最短路,ans[i],记录到达数字i需要多少步数.

#include <queue>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;

const int maxn = 1e4;
bool prime[maxn];
bool vis[maxn];
int a,b;
int ans[maxn];
int w[4] = {1000,100,10,1};

void find_prime() {
	for (int i=2; i<maxn; i++) prime[i] = 1;

	for (int i=2; i<=sqrt((double)maxn); i++) {
		for (int j=i*i; j<maxn; j += i) {
			prime[j] = 0;
		}
	}
}
void bfs() {
	memset(vis,0,sizeof vis);
	memset(ans,0,sizeof ans);
	queue<int> que;

	que.push(a);
	vis[a] = 1;

	while ( !que.empty() ) {
		int cur = que.front();
		que.pop();

		if (cur == b) return ;

		for (int i=0; i<4; i++) { //枚举四位数的所有操作
			int x = cur;
			// 求第i位的值
			x = x / w[i]; 
			x = x % 10; 
			//
			int num = cur - x * w[i]; //第i位为 0 的值
			for (int j=0; j<=9; j++) { // 开始改变i i位,
				if (i == 0 && j == 0) // 最高位不能为0, 例如0891
					continue;
				int sum = j * w[i] + num; // 枚举第i位后,的值
				//可能重复枚举,vis去重
				if (!vis[sum] && prime[sum]) {
					vis[sum] = 1;
					ans[sum] = ans[cur] + 1;
					que.push(sum);
				}
			}
		}

	}
	return ;
}
int main() {
//	freopen("a.txt","r",stdin);
	find_prime();
	
	int times;
	cin >> times;
	
	while (times--) {
		cin >> a >> b;
		bfs();
		cout << ans[b] << endl;
	}
	
	return 0;
}