算法
(宽度优先搜索)
可能的状态数有 $9!$ 种,所以暴搜即可,但这是个最短路问题,所以应该用宽搜实现。
记 $8$ 个棋子的放置情况记为 $s_1s_2 \cdots s_9$。若点 $i$ 上有棋子 $j$ 则令 $s_i=j$,否则令 $s_i = -1$。
若 $s_1s_2 \cdots s_9$ 通过所给的边进行若干次字符交换可使得它变成 12345678-1
,那么起点就是 $s_1s_2 \cdots s_9$,终点就是 12345678-1
。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::swap;
using std::vector;
using std::queue;
int main() {
int n = 9;
int m;
cin >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> s(n, -1);
rep(i, n-1) {
int p;
cin >> p;
--p;
s[p] = i;
}
vector<int> t(n, -1);
rep(i, n-1) t[i] = i;
map<vector<int>, int> dist;
queue<vector<int>> q;
dist[s] = 0;
q.push(s);
while (q.size()) {
s = q.front(); q.pop();
int d = dist[s];
rep(v, n) if (s[v] == -1) {
for (int u : to[v]) {
swap(s[u], s[v]);
if (dist.find(s) == dist.end()) {
dist[s] = d + 1;
q.push(s);
}
swap(s[u], s[v]);
}
}
}
if (dist.find(t) == dist.end()) puts("-1");
else cout << dist[t] << '\n';
return 0;
}
// 实现2:使用平板电视加速
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::swap;
using std::vector;
using std::queue;
int main() {
int n = 9;
int m;
cin >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> s(n, -1);
rep(i, n-1) {
int p;
cin >> p;
--p;
s[p] = i;
}
vector<int> t(n, -1);
rep(i, n-1) t[i] = i;
tree<vector<int>, int> dist;
queue<vector<int>> q;
dist[s] = 0;
q.push(s);
while (q.size()) {
s = q.front(); q.pop();
int d = dist[s];
rep(v, n) if (s[v] == -1) {
for (int u : to[v]) {
swap(s[u], s[v]);
if (dist.find(s) == dist.end()) {
dist[s] = d + 1;
q.push(s);
}
swap(s[u], s[v]);
}
}
}
if (dist.find(t) == dist.end()) puts("-1");
else cout << dist[t] << '\n';
return 0;
}
// 实现3:由于哈希表不支持 vector 到 int 的映射,所以需要用 string 来表示所有状态,
// 且用哈希表来维护距离会快很多
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::swap;
using std::vector;
using std::queue;
using std::string;
using std::unordered_map;
int main() {
int n = 9;
int m;
cin >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
string s(n, '9');
rep(i, n-1) {
int p;
cin >> p;
--p;
s[p] = i + '0';
}
string t(n, '9');
rep(i, n-1) t[i] = i + '0';
unordered_map<string, int> dist;
queue<string> q;
dist[s] = 0;
q.push(s);
while (q.size()) {
s = q.front(); q.pop();
int d = dist[s];
rep(v, n) if (s[v] == '9') {
for (int u : to[v]) {
swap(s[u], s[v]);
if (dist.find(s) == dist.end()) {
dist[s] = d + 1;
q.push(s);
}
swap(s[u], s[v]);
}
}
}
if (dist.find(t) == dist.end()) puts("-1");
else cout << dist[t] << '\n';
return 0;
}
# 🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂🐂