A1427 [2013 S6] 华容道

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n, m, q;
vector<vector<int>> cell;              // 1 = 该格上的棋子可以移动（0 = 固定）
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
vector<int> aroundCost;                // aroundCost[(u*4+d)*4+d']：空白格从 u 的第 d 个邻格绕到第 d' 个邻格的最少步数

bool inside(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

// 空白格从 (sx,sy) 出发、不能经过 blocked 的格子，求到各格的最短距离
vector<int> bfsAvoid(int sx, int sy, int blocked) {
    vector<int> dist(n * m, -1);
    if (!inside(sx, sy) || !cell[sx][sy]) return dist;
    queue<int> que;
    dist[sx * m + sy] = 0;
    que.push(sx * m + sy);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        int x = cur / m, y = cur % m;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!inside(nx, ny) || !cell[nx][ny]) continue;
            int nid = nx * m + ny;
            if (nid == blocked || dist[nid] != -1) continue;
            dist[nid] = dist[cur] + 1;
            que.push(nid);
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    cell.assign(n, vector<int>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> cell[i][j];

    // 预处理：空白格绕着某个棋子走的最短步数
    aroundCost.assign(n * m * 16, INF);
    for (int u = 0; u < n * m; u++) {
        if (!cell[u / m][u % m]) continue;
        for (int d = 0; d < 4; d++) {
            int sr = u / m + dx[d], sc = u % m + dy[d];
            if (!inside(sr, sc) || !cell[sr][sc]) continue;
            vector<int> dist = bfsAvoid(sr, sc, u);
            for (int d2 = 0; d2 < 4; d2++) {
                int tr = u / m + dx[d2], tc = u % m + dy[d2];
                if (!inside(tr, tc) || !cell[tr][tc]) continue;
                int t = tr * m + tc;
                if (dist[t] >= 0) aroundCost[(u * 4 + d) * 4 + d2] = dist[t];
            }
        }
    }

    while (q--) {
        int ex, ey, sx, sy, tx, ty;
        cin >> ex >> ey >> sx >> sy >> tx >> ty;
        --ex; --ey; --sx; --sy; --tx; --ty;
        int E = ex * m + ey, S = sx * m + sy, T = tx * m + ty;
        if (S == T) { cout << 0 << '\n'; continue; }

        // 初始：空白格先走到指定棋子的某个邻格
        vector<int> init = bfsAvoid(ex, ey, S);

        // 状态 (棋子位置 p, 空白格相对方向 d)
        vector<int> best(n * m * 4, INF);
        queue<int> que;
        for (int d = 0; d < 4; d++) {
            int nr = sx + dx[d], nc = sy + dy[d];
            if (!inside(nr, nc) || !cell[nr][nc]) continue;
            int t = nr * m + nc;
            if (init[t] < 0) continue;
            int st = S * 4 + d;
            best[st] = init[t];
            que.push(st);
        }

        int answer = INF;
        while (!que.empty()) {
            int st = que.front(); que.pop();
            int p = st / 4, d = st % 4;
            int cur = best[st];
            if (p == T) { answer = min(answer, cur); continue; }
            // 空白格绕着棋子走到别的方向
            for (int d2 = 0; d2 < 4; d2++) {
                int cost = aroundCost[(p * 4 + d) * 4 + d2];
                if (cost >= INF) continue;
                int ns = p * 4 + d2;
                if (best[ns] > cur + cost) { best[ns] = cur + cost; que.push(ns); }
            }
            // 指定棋子走进空白格所在的格子
            int nx = p / m + dx[d], ny = p % m + dy[d];
            if (!inside(nx, ny) || !cell[nx][ny]) continue;
            int np = nx * m + ny;
            int ns = np * 4 + (d ^ 2);          // 空白格跑到棋子原来的位置
            if (best[ns] > cur + 1) { best[ns] = cur + 1; que.push(ns); }
        }
        cout << (answer >= INF ? -1 : answer) << '\n';
    }
    return 0;
}