94 lines
2.8 KiB
C++
94 lines
2.8 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <deque>
|
||
#include <map>
|
||
#include <algorithm>
|
||
|
||
using namespace std;
|
||
|
||
// 正确的邻居表 (基于上下左右连接)
|
||
vector<int> adj[13] = {
|
||
{2}, // 0 -> 2
|
||
{2, 5}, // 1 -> 2, 5
|
||
{0, 1, 3, 6}, // 2 -> 0, 1, 3, 6
|
||
{2, 7}, // 3 -> 2, 7
|
||
{5}, // 4 -> 5
|
||
{1, 4, 6, 9}, // 5 -> 1, 4, 6, 9
|
||
{2, 5, 7, 10}, // 6 -> 2, 5, 7, 10
|
||
{3, 6, 8, 11}, // 7 -> 3, 6, 8, 11
|
||
{7}, // 8 -> 7
|
||
{5, 10}, // 9 -> 5, 10
|
||
{6, 9, 11, 12}, // 10 -> 6, 9, 11, 12
|
||
{7, 10}, // 11 -> 7, 10
|
||
{10} // 12 -> 10
|
||
};
|
||
|
||
int bfs(vector<int> from, vector<int> to) {
|
||
if (from == to) return 0;
|
||
|
||
map<vector<int>, int> mp;
|
||
deque<vector<int>> dqf, dqb;
|
||
|
||
dqf.push_back(from);
|
||
dqb.push_back(to);
|
||
mp[from] = 1;
|
||
mp[to] = -1;
|
||
|
||
while (!dqf.empty() && !dqb.empty()) {
|
||
bool forward = dqf.size() <= dqb.size();
|
||
deque<vector<int>>& dq = forward ? dqf : dqb;
|
||
|
||
vector<int> top = dq.front();
|
||
dq.pop_front();
|
||
int step = mp[top];
|
||
|
||
if (abs(step) > 10) continue;
|
||
|
||
for (int i = 0; i < 13; ++i) {
|
||
if (top[i] == 0) {
|
||
for (int neighbor : adj[i]) {
|
||
vector<int> next_v = top;
|
||
swap(next_v[i], next_v[neighbor]);
|
||
|
||
if (mp.count(next_v)) {
|
||
int recorded = mp[next_v];
|
||
if (forward && recorded < 0) {
|
||
int total = (step - 1) + abs(recorded);
|
||
if (total <= 20) return total;
|
||
}
|
||
else if (!forward && recorded > 0) {
|
||
int total = (abs(step) - 1) + recorded;
|
||
if (total <= 20) return total;
|
||
}
|
||
continue; // 同向相遇不处理
|
||
}
|
||
|
||
if (abs(step) < 11) {
|
||
mp[next_v] = forward ? step + 1 : step - 1;
|
||
dq.push_back(next_v);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
return -1;
|
||
}
|
||
|
||
int main() {
|
||
// 根据 HDU 3095 的目标状态：中间层左右两端是 0，其余按序排
|
||
// 另一种可能是样例所示：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0
|
||
const vector<int> end({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0});
|
||
|
||
int T;
|
||
if (!(cin >> T)) return 0;
|
||
while (T--) {
|
||
vector<int> pz(13);
|
||
for (int i = 0; i < 13; ++i) cin >> pz[i];
|
||
|
||
int x = bfs(pz, end);
|
||
if (x == -1 || x > 20) cout << "No solution!" << endl;
|
||
else cout << x << endl;
|
||
}
|
||
return 0;
|
||
}
|