68 lines
1.7 KiB
C++
68 lines
1.7 KiB
C++
#include <iostream>
|
||
#include <deque>
|
||
#include <unordered_map>
|
||
#include <string>
|
||
|
||
using namespace std;
|
||
|
||
// 逻辑修改：将 map 放在 BFS 内部或在每次调用前清空，确保每个测试用例独立
|
||
int bfs(string& from, const string& to) {
|
||
if (from == to) return 0;
|
||
|
||
unordered_map<string, int> mp; // 记录步数
|
||
deque<string> dq;
|
||
|
||
dq.push_back(from);
|
||
mp[from] = 0; // 初始步数为 0
|
||
|
||
while (!dq.empty()) {
|
||
string top = dq.front();
|
||
int step = mp[top];
|
||
dq.pop_front();
|
||
|
||
if (top == to) return step;
|
||
|
||
// 1. 尝试对每一位进行 +1 或 -1
|
||
for (int i = 0; i < 4; i++) {
|
||
for (int d : {1, -1}) {
|
||
string next_s = top;
|
||
int digit = next_s[i] - '0';
|
||
digit += d;
|
||
|
||
// 循环处理：1减1变9，9加1变1
|
||
if (digit == 0) digit = 9;
|
||
if (digit == 10) digit = 1;
|
||
|
||
next_s[i] = digit + '0';
|
||
if (mp.find(next_s) == mp.end()) {
|
||
mp[next_s] = step + 1;
|
||
dq.push_back(next_s);
|
||
}
|
||
}
|
||
}
|
||
|
||
// 2. 尝试交换相邻数字
|
||
for (int i = 0; i < 3; i++) { // 4位数字有3对相邻位
|
||
string next_s = top;
|
||
swap(next_s[i], next_s[i+1]);
|
||
|
||
if (mp.find(next_s) == mp.end()) {
|
||
mp[next_s] = step + 1;
|
||
dq.push_back(next_s);
|
||
}
|
||
}
|
||
}
|
||
return -1; // 理论上本题必有解
|
||
}
|
||
|
||
int main() {
|
||
int n;
|
||
if (!(cin >> n)) return 0;
|
||
while (n--) {
|
||
string a, b;
|
||
cin >> a >> b;
|
||
cout << bfs(a, b) << endl;
|
||
}
|
||
return 0;
|
||
}
|