题目：
给你两个四位的素数a，b。
a可以改变某一位上的数字变成c，但只有当c也是四位的素数时才能进行这种改变。
请你计算a最少经过多少次上述变换才能变成b。
例如：1033 -> 8179
1033
1733
3733
3739
3779
8779
8179
最少变换了6次。
输入：
第一行输入整数T，表示样例数。 (T <= 100)
每个样例输入两个四位的素数a，b。(没有前导零)
输出：
对于每个样例，输出最少变换次数，如果无法变换成b则输出"Impossible"。
样例：
分析：stoi不能用（RE），还有atoi，itoa（我编译环境（manjaro+Clion）下用不了）
用的stringstream
#include<iostream> #include<sstream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<functional> #include<iomanip> #include<numeric> #include<cmath> #include<queue> #include<vector> #include<set> #include<cctype> #define PI acos(-1.0) const int INF = 0x3f3f3f3f; const int NINF = -INF - 1; typedef long long ll; using namespace std; bool isp[10005]; bool used[10005]; string x, y; void isprime() { memset(isp, true, sizeof(isp)); for (int i = 4; i < 10000; i += 2) isp[i] = false; for (int i = 2; i < 10000; ++i) { if (isp[i]) { for (int j = i * i; j < 10000; j += i) isp[j] = false; } } } //int t = 0; int bfs() { queue<string> q; q.push(x); int d[10005]; memset(d, INF, sizeof(d)); stringstream s1; s1 << x; int num1; s1 >> num1; d[num1] = 0; while (q.size()) { string temp = q.front(); q.pop(); if (temp == y) break; stringstream s2; s2 << temp; int nx; s2 >> nx; //cout << nx << endl; //cout << endl; for (int i = 0; i < 4; ++i) { int r; if (i == 0) r = nx / 1000; else if (i == 1) r = nx / 100 % 10; else if (i == 2) r = nx / 10 % 10; else r = nx % 10; //cout << r << endl; for (int j = 0; j < 10; ++j) { if (j == 0 && i == 0) continue; if (j == r) continue; //cout << '*' << j << endl; int num; if (i == 0) num = j * 1000 + nx % 1000; else if (i == 1) num = nx / 1000 * 1000 + j * 100 + nx % 100; else if (i == 2) num = nx / 100 * 100 + j * 10 + nx % 10; else num = nx / 10 * 10 + j; //cout << num << endl; if (isp[num] && !used[num]) { //t++; used[num] = true; d[num] = d[nx] + 1; string s; stringstream ss; ss << num; ss >> s; q.push(s); } } } } //cout << t << endl; stringstream s3; s3 << y; int num3; s3 >> num3; return d[num3]; } int main() { int T; cin >> T; isprime(); while (T--) { cin >> x >> y; memset(used, false, sizeof(used)); int num = bfs(); if (num == INF) cout << "Impossible" << endl; else cout << num << endl; } return 0; }