ABC243

ABC224

D

题目大意

有一个九个点的无向图棋盘，上面有八个棋子，一次操作能将一个棋子沿边移到空点上，问将每个棋子移到与它编号相同的点最少几步。
解题思路

考虑使用 BFS。
用 string 存储状态，\(s_i\) 表示 \(i\) 号格点上棋子的编号，\(0\) 表示没有棋子。
注意：一开始不能直接修改 \(s_i\)，因为 \(s\) 是空串，修改一直都是空串，需要初始化为  000000000。
利用 unordered_map 判断此状态是否访问过，用 map 会 TLE。
每次找到字符串中的 \(0\)，用链式向前星遍历相邻点，然后交换两者位置，没有访问过放入队列即可。
如果找到状态为  123456780，就输出答案，没有说明无解，输出 \(-1\)。
代码

[code]#include#define endl "\n"using namespace std;const int N = 40;struct edge{        int to, next;} e[N > m;        for (int i = 1; i > u >> v;                add(u, v), add(v, u);        }        for (int i = 1; i > x;                s[x] = '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")                {                        cout  w >> 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[q.x][0])                {                        dp[q.id] = a[q.x][0] + 1;                        c[q.x][1] = c[q.x][0];                        c[q.x][0] = q.w;                        a[q.x][1] = a[q.x][0];                }                else                {                        dp[q.id] = a[q.x][1] + 1;                }                if (q.w < d[q.y][0])                {                        dp[q.id] = max(dp[q.id], b[q.y][0] + 1);                        d[q.y][1] = d[q.y][0];                        d[q.y][0] = q.w;                        b[q.y][1] = b[q.y][0];                }                else                {                        dp[q.id] = max(dp[q.id], b[q.y][1] + 1);                }                a[q.x][0] = max(a[q.x][0], dp[q.id]);                b[q.y][0] = max(b[q.y][0], dp[q.id]);        }        for (int i = 1; i  t >> a >> b;        if (s == t)        {                cout