当年我省只有vfk一人AC此题（其实是AK），学长记载的时候猜测他一定用了很高级的算法。做完之后发现特定算法方面它只用到了BFS和SPFA，不禁想起自己去年NOIP，三个小时没做出一道DFS（得了10分）。
读完题后，判断它是搜索。棋子的移动等价于空格的移动。要不要使用启发式搜索？怎样表示一个状态？我发现只要标记出空格的位置和指定棋子的位置。这样一来，状态只有不到810000个，60分应该有了。500次查询是怎么回事？4亿多的计算量……启发式搜索能让有解的情况快一点，无解还是得搜索整个状态空间。这是一个上界，也许实际情况达不到这么坏？然而，吃过几次亏了，对数据没有明确说明的特性不要乱假设……
和WZH学长交流了一下，结果他看题解去了（嘿嘿）……看完题解的WZH学长，每句话都带着强烈的启发性。虽然不是很明白他在说什么，但他强调了四连通。
先回到自己的思路。如果使用启发式搜索，启发函数我会选择指定棋子到终点的曼哈顿距离。这样不能体现空格和棋子之间的联系，移动的是空格，然而醉翁之意不在酒，棋子才是我的目标。如果开局的时候空格离指定棋子很远，会扩展出很多无用的状态，因为是让空格走，这个不影响启发函数。也许我应该把空格和棋子的距离加入启发函数？这样仍然不能避免无解时搜索整个状态空间。我也考虑过让空格先走到棋子附近，再搜索，把空格处于四连通或八连通位置作为初始状态。W学长的话又促使我思考，发现四连通就够了。但是还是禁不住巨大的搜索量。
我得从根本上加以改进，减少状态数。先前想的那些策略，都是为了让空格尽量接近棋子，不走冤枉路，不喧宾夺主。能不能让棋子自己主导搜索？它想往旁边移一格，怎么办？借助于空格。空格先到那里，再和它交换一下位置。必须是这样。是否可以规定状态中棋子和空格是相邻的？这样使状态数减少到3600个。怎么扩展呢？每次BFS？很可能会搜索整个棋盘，不优。联想到题目中一个有点怪的约定：每组数据中棋盘是固定的，变的只是开局时空格的位置和游戏的指定棋子起始、终止的位置。方便了预处理。
然后写代码。一开始有点不专心，造成了之后调试的困难。考虑不周……我写着写着才发现要用SPFA。还有其他错误：字母打错、不必要的限制条件、改了一处错误却没改配套的地方、SPFA使用了struct Node里的dist而不是更新后的、在外面加点忘记置inq为true、初始化数组的位置不对、莫名地在每次询问后把预处理出来的cost数组清零了（是说大数据怎么一堆-1……）。手里有数据，我是对着数据调的，作弊啦。练习了一下GDB的使用。一开始，学长推荐GDB，我是拒绝的。最近发现还是挺方便，可以让程序在恰当的地方停下来，查看一些变量。要综合百家之长啊。
对于我的代码做一些说明。两个idx函数用于把多个维度压缩成一维，因为状态数比较少，就没有用哈希表。namespace pre有两个用处：一是用于预处理，修改dist数组，在main里面用这些信息计算cost；二是用于让空格走到棋子附近。发现它们的需求是相似的，就共用了一段代码。namespace search用于针对每一局来search，状态之间转移的代价来自cost。在W学长的提醒下加上了对起点终点是否重合的判断。
#include <cstdio> #include <queue> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}, INF = 0x3f3f3f3f; int n, m, cost[1<<14], dist[32][32]; bool M[32][32]; // 棋子在(i, j)，空格在k方向，棋子转移到p方向 inline int idx(int i, int j, int k, int p) { return i<<9 | j<<4 | k<<2 | p; } // 棋子在(i, j)，空格在k方向 inline int idx(int i, int j, int k) { return i<<7 | j<<2 | k; } namespace pre { struct Node { int r, c; }; // 从(r, c)到(r1, c1)周围四连通的位置，且不过(r1, c1)；至多有cnt个目标点 void cal(int r, int c, int r1, int c1, int cnt) { memset(dist, -1, sizeof(dist)); M[r1][c1] = false; queue<Node> Q; Q.push((Node){r, c}); dist[r][c] = 0; Node u; while (!Q.empty()) { u = Q.front(); Q.pop(); if (abs(u.r-r1) == 1 && abs(u.c-c1) == 1) { if (--cnt == 0) break; } for (int i = 0; i < 4; ++i) { Node v = (Node){u.r+dr[i], u.c+dc[i]}; if (M[v.r][v.c] && dist[v.r][v.c] == -1) { dist[v.r][v.c] = dist[u.r][u.c] + 1; Q.push(v); } } } M[r1][c1] = true; } } namespace search { struct Node { int r, c, dir; }; int d[1<<12]; bool inq[1<<12]; int spfa(int ti, int tj, queue<Node>& Q) { Node u; while (!Q.empty()) { u = Q.front(); Q.pop(); int hu = idx(u.r, u.c, u.dir); inq[hu] = false; for (int k = 0; k < 4; ++k) { Node v = (Node){u.r+dr[k], u.c+dc[k], k^1}; int c = cost[idx(u.r, u.c, u.dir, k)], hv = idx(v.r, v.c, v.dir); if (M[v.r][v.c] && c && d[hv] > d[hu] + c) { d[hv] = d[hu] + c; if (!inq[hv]) { Q.push(v); inq[hv] = true; } } } } int ans = INF; for (int k = 0; k < 4; ++k) ans = min(ans, d[idx(ti, tj, k)]); return ans == INF ? -1 : ans; } } int main() { int q; scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { int x; scanf("%d", &x); M[i][j] = x; } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (M[i][j]) // blank for (int k = 0; k < 4; ++k) { int i1 = i+dr[k], j1 = j+dc[k]; // 棋子 if (M[i1][j1]) { pre::cal(i, j, i1, j1, 4); for (int p = 0; p < 4; ++p) { int i2 = i1+dr[p], j2 = j1+dc[p]; // 目标 if (dist[i2][j2] != -1) { cost[idx(i1, j1, k^1, p)] = dist[i2][j2] + 1; } } } } int ei, ej, si, sj, ti, tj; while (q--) { using namespace search; scanf("%d %d %d %d %d %d", &ei, &ej, &si, &sj, &ti, &tj); if (si == ti && sj == tj) { puts("0"); continue; } pre::cal(ei, ej, si, sj, 4); memset(d, 0x3f, sizeof(d)); queue<Node> Q; for (int k = 0; k < 4; ++k) { int i = si+dr[k], j = sj+dc[k]; if (dist[i][j] != -1) { Q.push((Node){si, sj, k}); inq[idx(si, sj, k)] = true; d[idx(si, sj, k)] = dist[i][j]; } } printf("%d\n", spfa(ti, tj, Q)); } return 0; }体会：大胆构思，仔细实现。
