「NOIP2013」华容道

solution by XiangXunYi

题目描述

给你一张华容道，有障碍格，共 \(q\) 次询问，每次指定一个起点，终点和空格，问最少需要多少步让起点棋子移到终点。

思路推导

step 1

先思考暴力，发现状态与当前格子和空格的位置有关系，同时问最少步数，故采用最短路，定义 \(dis_{x,y,p,q}\) 表示当前格子位置 \((x,y)\) ，空格位置 \((p,q)\) 的最短路。
时间复杂度 \(O(n^4T)\)。

step 2

我们可以发现只动一个格子且只有当空格在其附近才能动，所以只有空格与该格子四联通时的状态是有意义的，所以可以将后两位的 \(p,q\) 改为 \(p \in \{0,1,2,3\}\)，即定义 \(dis_{x,y,0/1/2/3}\) 表示当前格子在 \((x,y)\) ，空格在其上/下/左/右 时的最短路，因为边少，使用 dijkstra 更优，接下来考虑建图。

step 3

对于一个格子和其附近空格，有两种情况：

• 交换空格与格子，即从 \(i,j,p\) 向 \(i+dx[p],j+dy[p],p \bigoplus 1\) 连边
• 改变空格的位置，即从 \(i,j,p\) 向 \(i,j,q\) 连边

对于第一种情况，显然边权为 \(1\)，但对于第二种情况，要在不交换 \(i,j\) 的情况下将空格从相对位置 \(p\) 交换到相对位置 \(q\)，可以采取 bfs 且指定一点不能走（后面还有用）。
明显一开始空格可能不在其四联通分量中，所以要将空格移过来，枚举空格相对位置，并限制不能走到 \((sx,sy)\)，将答案加上在此情况下的最短路，即是最终答案。
tips： 当 \((sx,sy) \neq (tx,ty)\) 时才需要将空格迁移。

solution

定义 \(dis_{i,j,p}\) 表示格子在 \((i,j)\)，空格相对在其上/下/左/右时的最短路，跑 dijkstra，预处理 \(f_{i,j,p,x,y}\) 表示点 \((i,j)\) 在不经过其上/下/左/右时到达 \((x,y)\) 的最短路，最终答案为 \(min^4_{p=1} \{ dis_{tx,ty,p} \} + min^4_{p=1} \{ f_{sx+dx[p],sy+dy[p],p^1,tx,ty} \}\) 。

代码

文字不多，代码挺长，自己打调还是难，不是同学帮忙估计还要多 \(1\) ~ \(2 h\) 。

/*
address:https://www.becoder.com.cn/problem/9288 or https://www.luogu.com.cn/problem/P1979
AC 2024/11/27 15:26
*/
#include<bits/stdc++.h>
using namespace std;
const int dx[] = { 0,0,1,-1,0 }, dy[] = { 1,-1,0,0,0 };
const int N = 35, M = N * N << 2;
const int INF = 0x3f3f3f3f;
int n, m, Q;
int a[N][N];
struct edge {
    int to, w;
};
vector<edge>G[M];
int dist[M];
bool vis[M];
struct node {
    int u, dist;
    bool operator < (const node& o)const { return dist > o.dist; }
};
priority_queue<node>qq;
inline void dijkstra(int s) {
    fill(dist + 1, dist + (n * m << 2) + 1, INF);
    fill(vis + 1, vis + (n * m << 2) + 1, false);
    dist[s] = 0;
    qq.push({ s,0 });
    while (!qq.empty()) {
        int u = qq.top().u;
        qq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : G[u])
            if (dist[e.to] > dist[u] + e.w) {
                dist[e.to] = dist[u] + e.w;
                qq.push({ e.to,dist[e.to] });
            }
    }
}
inline bool check(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && a[x][y] == 1; }
int cnt;
int dis[N][N];
pair<int, int> qqq[N * N];
inline void bfs(int s, int t, int nx, int ny) {
    int l = 1, r = 1;
    qqq[r++] = { s,t };
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++) dis[i][j] = 0x3f3f3f3f;
    dis[s][t] = 0;
    while (l < r) {
        int x = qqq[l].first, y = qqq[l].second;
        l++;
        for (int i = 0;i < 4;i++) {
            int kx = x + dx[i], ky = y + dy[i];
            if (!check(kx, ky) || kx == nx && ky == ny || dis[kx][ky] != 0x3f3f3f3f) continue;
            dis[kx][ky] = dis[x][y] + 1;
            qqq[r++] = { kx,ky };
        }
    }
}
int f[N][N][4][N][N], id[N][N][4];
int main() {
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++) scanf("%d", &a[i][j]);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            if (check(i, j))
                for (int k = 0;k < 4;k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (check(x, y)) {
                        bfs(i, j, x, y);
                        for (int p = 1;p <= n;p++)
                            for (int q = 1;q <= m;q++)
                                f[i][j][k][p][q] = dis[p][q];
                    }
                }
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            if (check(i, j))
                for (int p = 0;p < 4;p++)
                    if (check(i + dx[p], j + dy[p]))
                        id[i][j][p] = ++cnt;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            if (check(i, j))
                for (int p = 0;p < 4;p++) {
                    if (check(i + dx[p], j + dy[p])) {
                        for (int q = 0;q < 4;q++)
                            if (p != q && check(i + dx[q], j + dy[q]))
                                G[id[i][j][p]].push_back({ id[i][j][q],f[i + dx[p]][j + dy[p]][p ^ 1][i + dx[q]][j + dy[q]] });
                        G[id[i][j][p]].push_back({ id[i + dx[p]][j + dy[p]][p ^ 1],1 });
                    }
                }
    while (Q--) {
        int ex, ey, sx, sy, tx, ty;scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
        int ans = 0x3f3f3f3f;
        for (int p = 0;p < 4;p++) {
            if (!check(sx + dx[p], sy + dy[p])) continue;
            int cur = (sx == tx && sy == ty) ? 0 : f[sx + dx[p]][sy + dy[p]][p ^ 1][ex][ey];
            dijkstra(id[sx][sy][p]);
            int mn = 0x3f3f3f3f;
            for (int q = 0;q < 4;q++)
                if (check(tx + dx[q], ty + dy[q])) mn = min(mn, dist[id[tx][ty][q]]);
            cur += mn;
            ans = min(ans, cur);
        }
        printf("%d\n", ans >= 0x3f3f3f3f ? -1 : ans);
    }
    return 0;
}

特别鸣谢 XiangXunYi 帮调。