代码:
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <queue>
#include <utility>
#include <iterator>

using namespace std;
const int Maxn = 10005;
int T;
bool isprime[Maxn];
bool vis[Maxn];
typedef pair < string, int> node;

string a, b;

inline void prime_sieve(int n) {
	memset(isprime, 1, sizeof isprime);
	int i, j;
	isprime[0] = 0, isprime[1] = 0;
	for (i = 2; i <= n; ++i) {
		if (isprime[i])
			for (j = i + i; j <= n; j += i)
				isprime[j] = 0;
	}
}

inline int strtonum(string x) {
	int num = 0, i;
	if (x[0] == '-') {
		for (i = 1; i < x.length(); ++i)
			num = num * 10 + (x[i] - '0');
		return -num;
	}
	for (i = 0; i < x.length(); ++i)
		num = num * 10 + (x[i] - '0');
	return num;
}

inline bool check(int num) {
	if (num == strtonum(b)|| (num & 1 && isprime[num] && vis[num] == 0 && num >= 0 && num <= 9999))
		return true;
	return false;
}

inline int bfs() {

	queue < node > Q;
	node x;
	x.first = a, x.second = 0;
	Q.push(x);
	vis[strtonum(x.first)] = 1;

	int i, j, numberx;
	node next;
	while (!Q.empty()) {
		x = Q.front(); Q.pop();
		if (x.first == b) return x.second;
		for (i = 0; i < 4; ++i) {
			if (i == 0) {
				for (j = 1; j <= 9; ++j) {
					next = x;
					next.first[0] = (j + '0');
					numberx = strtonum(next.first);
					if (check(numberx)) {
						vis[numberx] = 1;
						next.second = x.second + 1;
						Q.push(next);
					}
				}
			} else if (i == 1) {
				for (j = 0; j <= 9; ++j) {
					next = x;
					next.first[1] = (j + '0');
					numberx = strtonum(next.first);
					if (check(numberx)) {
						vis[numberx] = 1;
						next.second = x.second + 1;
						Q.push(next);
					}
				}
			} else if (i == 2) {
				for (j = 0; j <= 9; ++j) {
					next = x;
					next.first[2] = (j + '0');
					numberx = strtonum(next.first);
					if (check(numberx)) {
						vis[numberx] = 1;
						next.second = x.second + 1;
						Q.push(next);
					}
				}
			} else if (i == 3) {
				for (j = 1; j <= 9; j += 2) {
					next = x;
					next.first[3] = (j + '0');
					numberx = strtonum(next.first);
					if (check(numberx)) {
						vis[numberx] = 1;
						next.second = x.second + 1;
						Q.push(next);
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	prime_sieve(Maxn);
	cin >> T;
	while (T--) {
		memset(vis, 0, sizeof vis);
		cin >> a >> b;
		int X;
		X = bfs();
		if (X == -1) cout << "Impossible" << endl;
		else cout << X << endl;
	}
	return 0;
}
诡异啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

• Re:g++ tle, c++ac球原因 (2948) ethan1 2022-10-17 21:54:10