POJ 3126 Prime Path 题解 《挑战程序设计竞赛》

POJ 3126 Prime Path

换门牌：从from换到to，每次只能换一个数字，每次都是素数。求最小次数？

2.6 数学问题的解题窍门

素数

艾氏筛法bfs。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <queue>
using namespace std;

#define MAX_N 9999 + 16

int  prime[MAX_N];			// 第i个素数
bool is_prime[MAX_N + 1];	//is_prime[i]为真的时候表示i为素数
int sieve(const int& n)
{
	int p = 0;
	fill(is_prime, is_prime + n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; ++i)
	{
		if (is_prime[i])
		{
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
	return p;
}

int dp[MAX_N];

// 将number的倒数第digit位改成change
int get_next(int number, int digit, int change) 
{
	switch (digit) 
	{
		case 0:
			return number / 10 * 10 + change;
		case 1:
			return number / 100 * 100 + number % 10 + change * 10;
		case 2:
			return number / 1000 * 1000 + number % 100 + change * 100;
		case 3:
			return number % 1000 + change * 1000;
	}
	return 0;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// 先做一份素数表
	sieve(MAX_N);
	int N;
	cin >> N;
	while (N--)
	{
		int from, to;
		cin >> from >> to;
		// dfs
		memset(dp, 0x3f, sizeof(dp));
		dp[from] = 0;
		queue<int> q;
		q.push(from);
		while (q.size())
		{
			const int current = q.front(); q.pop();
			for (int i = 0; i < 4; ++i)
			{
				for (int j = 0; j < 10; ++j)
				{
					if (i == 3 && j == 0)
					{
						// 将第一位改成0是无意义的
						continue;
					}
					int next = get_next(current, i, j);
					if (is_prime[next] == false || dp[next] <= dp[current])
					{
						// 不是素数不行，如果到next已经有更小的那也不用这个变换路径了
						continue;
					}
					dp[next] = dp[current] + 1;
					q.push(next);
				}
			}
		}
		cout << dp[to] << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3126 Prime Path 题解 《挑战程序设计竞赛》