ABC243
ABC224D
题目大意
有一个九个点的无向图棋盘，上面有八个棋子，一次操作能将一个棋子沿边移到空点上，问将每个棋子移到与它编号相同的点最少几步。
解题思路
考虑使用 BFS。
用 string 存储状态，\(s_i\) 表示 \(i\) 号格点上棋子的编号，\(0\) 表示没有棋子。
注意：一开始不能直接修改 \(s_i\)，因为 \(s\) 是空串，修改一直都是空串，需要初始化为000000000。
利用 unordered_map 判断此状态是否访问过，用 map 会 TLE。
每次找到字符串中的 \(0\)，用链式向前星遍历相邻点，然后交换两者位置，没有访问过放入队列即可。
如果找到状态为123456780，就输出答案，没有说明无解，输出 \(-1\)。
代码
#include#define endl "\n"using namespace std;const int N = 40;struct edge{ int to, next;} e = '0' + i; } q.push(make_pair(s, 0)); mp = 1; while (!q.empty()) { s = q.front().first; int x = q.front().second; q.pop(); if (s == " 123456780") { coutw >> n; for (int i = 1; i > q.x >> q.y >> q.w; q.id = i; } sort(q + 1, q + n + 1, cmp); memset(a, -1, sizeof a); memset(b, -1, sizeof b); memset(c, 0x7f, sizeof c); memset(d, 0x7f, sizeof d); for (int i = n; i >= 1; i--) { if (q.w < c.x]) { dp.id] = a.x] + 1; c.x] = c.x]; c.x] = q.w; a.x] = a.x]; } else { dp.id] = a.x] + 1; } if (q.w < d.y]) { dp.id] = max(dp.id], b.y] + 1); d.y] = d.y]; d.y] = q.w; b.y] = b.y]; } else { dp.id] = max(dp.id], b.y] + 1); } a.x] = max(a.x], dp.id]); b.y] = max(b.y], dp.id]); } for (int i = 1; it >> a >> b; if (s == t) { cout
页:
[1]