poj3126-Prime Path(BFS)

发布于 2019-07-24  540 次阅读


问题传送门:

题意:

给你两个四位数的质数a, b, 对a进行操作使之变成b 
每一次操作只能该改变 a 的一个位,并且改变后的数必须是一个质数
问最少的操作次数是多少。

分析:

因为必须是四位数的质数,所以先看看1000-10000的质数一共有多少个
把这些质数放入一个数组中,一共才1000多个。
暴力搜索没有问题,最少操作次数,最短路这种问题用BFS暴力最方便。
每一次把我们筛选出来的质数中,与上一质数只有一位不同的所有质数全部加入到队列
并且把这些数标记,下次遇到的时候就不用再加入队列了。
当搜索到答案时返回步数。
当直到队列为空也没有搜索到答案,返回-1.

代码:

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct Node
{
	int num, step;
} t, nt;

int prm[10000], cnt;
int vis[10000];
bool isprime(int n)
{
	if (n == 1 || n == 0) return false;
	if (n == 2 || n == 3) return true;
	if (n%6 != 1 && n%6 != 5) return false;
	int t = sqrt(n);
	for (int i = 5; i <= t; i++)
	{
		if (n%i == 0 || n%(i+2)==0)
			return false;
	}
	return true;
}

void init()
{
	cnt = 0;
	for (int i = 1000; i < 10000; i++)
		if (isprime(i))
			prm[cnt++]=i;
}

bool judge(int num1, int num2)
{
	if (vis[num2]) return false;
	int cntt = 0;
	while (num1 && num2)
	{
		if (num1%10==num2%10) cntt++;
		num1 /= 10, num2 /= 10;
	}
	if(cntt==3)
		return true;
	return false;
}

queue <Node> q;
int BFS(int a, int b)
{
	if (a == b) return 0;
	t.num = a, t.step = 0;
	q.push(t);
	while (!q.empty())
	{
		t = q.front();
		q.pop();
		for (int i = 0; i < cnt; i++)
		{
			nt.num = prm[i];
			nt.step = t.step + 1;
			if (judge(t.num, nt.num))
			{
				if (nt.num == b)
					return nt.step;

				q.push(nt);
				vis[nt.num] = 1;
			}
		}
	}
	return -1;
}

void clean()
{
	for (int i = 1000; i < 10000; i++)
		vis[i] = 0;
	while (!q.empty()) q.pop();
}

int main()
{
	init();
	int T, a, b;
	cin >> T;
	while (T--)
	{
		clean();
		cin >> a >> b;
		int ans = BFS(a, b);
		if (ans == -1)
			cout << "Impossible" << endl;
		else
			cout << ans << endl;	
	}	
	return 0;
}

Simple And Clear