【题解】Prime Path

题目: [Prime Path](《20级计科ACM程序设计》–搜索入门 - Virtual Judge (sdtbu.edu.cn))

题意:

给两个4位素数n, m. 每次可以改变n的4个位置中的某个数, 问最少几次可以得到m.

思路:

• 依然是裸BFS, 注意一下队列中存pair, second是当前走了几步.
• 需要提前将所有4位素数筛选出来.
• 还有一种做法: 可以遍历队列中每个数的4个位置的9种可能, 但是因为涉及到int转string, 写起来比较麻烦, 还要特判第一位不能为0.
• 纯路人, 这人写的代码真优雅~

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<map>

using namespace std;

const int N = 10010;
#define ll long long
#define PII pair<int,int>

vector<int>p;//存1000-9999的素数
int n, m;

//欧拉筛法, 找到所有4位的素数, 存在p数组中
void prime()
{
	int cnt = 0, p1[N]={0}, v[N]={0};
	for (int i = 2; i <= 9999; ++i)
	{
		if (!v[i])p1[cnt++] = i;
		if (i >= 1000 && !v[i])p.push_back(i);
		

		for (int j = 0; p1[j] * i <= 9999; ++j)
		{
			v[p1[j] * i] = 1;
			if (i % p1[j] == 0) break;
		}
	}
    
    return;
}

bool cherk(int a, int b)
{
	int k = 0;
	//逐位比较, 只要有三个数字位置大小均相同, 那么就代表符合条件
	for (int i = 0; i <= 3 && a && b; ++i)
	{
		if (a % 10 == b % 10)k++;
		//cout << a % 10 << " " << b % 10 << endl;
		a /= 10, b /= 10;
	}

	return k == 3 ? true : false;
}

int BFS()
{
	queue<PII>q;
	//n是初始素数, m是最终素数. second记录走了多少步, 初始为0.
	q.push(PII(n, 0));
	bool st[N] = { 0 };
	st[n] = 1;

	while (q.size())
	{
		PII t = q.front();
		q.pop();
		if (t.first == m)return t.second;
	
		for (int i = 0; i < p.size(); ++i)
		{
			//检查第i个素数是否从未入队并且可以只改变一个字符得到
			if (st[p[i]]==0 && cherk(p[i], t.first))
			{
				q.push(PII(p[i], t.second + 1));
				st[p[i]] = 1;
			}
		}
	}
	
	return -1;
}

int main()
{
	prime();
	//for (int i = 0; i < p.size(); ++i) cout << p[i] << " ";
	
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int res=BFS();
		res >= 0 ? cout << res << endl : cout<<"Impossible"<<endl;
	}
	
	return 0;
}