思路与算法

压缩为指定棋子位置和空格相对邻居方向的4nm种状态。固定指定棋子，对空格绕行距离做BFS预处理；绕行和交换构成带权状态图。每次询问先BFS把初始空格接入这些状态，再Dijkstra求指定棋子到目标的最少总步数。

正确性说明

只有空格与指定棋子相邻时，下一次交换才能改变指定棋子位置。两次这种交换之间，指定棋子不动，其他棋子无须区分，空格在删去该位置的网格里按最短路绕行即可，所以这段操作可由BFS距离压缩且不会损失最优解。交换花1步并令空格处在旧指定棋子位置，对应相反方向状态。初始BFS覆盖第一次交换前全部可能绕行，之后所有压缩边权非负，Dijkstra得到最短真实移动序列长度。

复杂度

令V=nm<=900。预处理O(V²)时间、O(V)大小的稀疏压缩图及O(V)临时空间（每点方向为常数）；每次询问O(V log V)时间、O(V)额外空间，含初始BFS、Dijkstra距离表与优先队列初始化。总O(V²+qV log V)时间、O(V)空间。

易错点

固定的是棋盘0格子，指定棋子与空格的初始位置每次都变；BFS空格绕路时必须禁止穿过指定棋子，否则会低估步数。指定棋子已经在目标时答案0，无法绕行或不同连通块时输出-1；迭代BFS避免递归。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, m, Q;
    cin >> n >> m >> Q;
    int V = n * m;
    vector<int> a(V);
    for (int &x : a)
        cin >> x;
    vector<array<int, 4>> nb(V);
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    for (int s = 0; s < V; s++)
        for (int d = 0; d < 4; d++) {
            int x = s / m + dx[d], y = s % m + dy[d];
            nb[s][d] = (x >= 0 && x < n && y >= 0 && y < m && a[x * m + y]) ? x * m + y : -1;
        }
    auto bfs = [&](int E, int S) {
        vector<int> dist(V, -1), q(1, E);
        dist[E] = 0;
        for (int i = 0; i < (int)q.size(); i++)
            for (int v : nb[q[i]])
                if (v >= 0 && v != S && dist[v] < 0) {
                    dist[v] = dist[q[i]] + 1;
                    q.push_back(v);
                }
        return dist;
    };
    vector<vector<pair<int, int>>> g(V * 4);
    for (int s = 0; s < V; s++)
        if (a[s])
            for (int d = 0; d < 4; d++)
                if (nb[s][d] >= 0) {
                    int v = nb[s][d];
                    g[s * 4 + d].push_back({v * 4 + (d ^ 1), 1});
                    auto dist = bfs(v, s);
                    for (int e = 0; e < 4; e++)
                        if (e != d && nb[s][e] >= 0 && dist[nb[s][e]] >= 0)
                            g[s * 4 + d].push_back({s * 4 + e, dist[nb[s][e]]});
                }
    while (Q--) {
        int ex, ey, sx, sy, tx, ty;
        cin >> ex >> ey >> sx >> sy >> tx >> ty;
        int E = (ex - 1) * m + ey - 1, S = (sx - 1) * m + sy - 1, T = (tx - 1) * m + ty - 1;
        if (S == T) {
            cout << 0 << "\n";
            continue;
        }
        auto initial = bfs(E, S);
        const int INF = 1000000000;
        vector<int> d(4 * V, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int k = 0; k < 4; k++)
            if (nb[S][k] >= 0 && initial[nb[S][k]] >= 0) {
                d[S * 4 + k] = initial[nb[S][k]];
                pq.push({d[S * 4 + k], S * 4 + k});
            }
        int ans = -1;
        while (!pq.empty()) {
            auto u = pq.top();
            pq.pop();
            if (u.first != d[u.second])
                continue;
            if (u.second / 4 == T) {
                ans = u.first;
                break;
            }
            for (auto e : g[u.second])
                if (d[e.first] > u.first + e.second) {
                    d[e.first] = u.first + e.second;
                    pq.push({d[e.first], e.first});
                }
        }
        cout << ans << "\n";
    }
}