[数据结构与算法]2021-08-03

poj3126题解与思考 Prime Path

在写题意之前允许我感叹一下，这道题难了我挺久的，想不到把他攻克是如此的快乐！经历了卡住的痛苦，想看题解，真的感谢自己当时忍住了，拿出笔分析了一下，发现自己的卡住的地方，加了队列后解决了存取数字的问题，不然一直没想通，想过加数组但不行。可能当时还是抱着看题解就毁了这道题，没了自己的思考，事实上我和题解的思路确实不同。纪念一下这种感觉！Accepted！

1. 题意：
   给定两个四位数（都是素数）a,b，每次只能换一个数字，求从a到b的最短更换次数，且每次更换完后仍是素数。

2. 知识点：涉及bfs,判断素数的方法（大数）

3. 代码：

//AC! <Prime Path>
#include<iostream>
#include<queue>
using namespace std;

struct number {
	int prime;//数字（路径）
	int step;//记录步数
};
bool vis[10000];//记录是否访问
int a, b;

//判断是否是素数
bool Judge(int n) {
	if (n % 2 == 0) {
		return false;
	}
	else {
		//素数一定是奇数，且只需要判断到根号n
		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0) return false;
		}
	}
	return true;
}

void LeastStep(int a, int b) {
	vis[a] = true;
	number x;
	x.prime = a;
	x.step = 0;
	queue<number> q;
	q.push(x);
	while (!q.empty()) {
		number n = q.front();
		q.pop();
		if (n.prime == b) {
			cout << n.step << endl;
			return;
		}
		//枚举个位，排除偶数
		for (int i = 1; i <= 9; i += 2) {
			int y = n.prime - (n.prime) % 10 + i;
			if (Judge(y) && y != n.prime && !vis[y]) {
				vis[y] = true;
				number m;
				m.prime = y;
				m.step = n.step + 1;
				q.push(m);
			}
		}

		//枚举十位
		for (int i = 0; i <= 9; i++) {
			int y = n.prime - ((n.prime) / 10 % 10) * 10 + i * 10;
			if (Judge(y) && y != n.prime && !vis[y]) {
				vis[y] = true;
				number m;
				m.prime = y;
				m.step = n.step + 1;
				q.push(m);
			}
		}

		//枚举百位
		for (int i = 0; i <= 9; i++) {
			int y = n.prime - ((n.prime) / 100 % 10) * 100 + i * 100;
			if (Judge(y) && y != n.prime && !vis[y]) {
				vis[y] = true;
				number m;
				m.prime = y;
				m.step = n.step + 1;
				q.push(m);
			}
		}

		//枚举千位
		for (int i = 1; i <= 9; i++) {
			int y = n.prime - ((n.prime) / 1000) * 1000 + i * 1000;
			if (Judge(y) && y != n.prime && !vis[y]) {
				vis[y] = true;
				number m;
				m.prime = y;
				m.step = n.step + 1;
				q.push(m);
			}
		}
	}
	cout << "Impossible" << endl;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		cin >> a >> b;
		memset(vis, false, sizeof(vis));
		LeastStep(a, b);
	}
	return 0;
}