题解：多棋子移动最小步数问题

算法思路

本题要求将多个棋子从初始位置移动到目标位置，要求移动过程中不能有多个棋子同时在同一格，且步数最小。这是一个典型的带权二分图匹配问题。

1. 问题分析

• 棋子移动规则：从 $(x, y)$ 可以走到 8 个方向：$(x±a, y±b)$ 和 $(x±b, y±a)$ 的组合
• 约束条件：任何时刻不能有两个棋子在同一格子
• 目标：最小化总步数

2. 关键转化

将问题转化为二分图最小权匹配：

• 左部：初始棋子位置（共 $k$ 个）
• 右部：目标棋子位置（共 $k$ 个）
• 边权：从初始位置到目标位置的最短步数（负数，因为 KM 算法求最大权匹配）

3. 算法步骤

1. 预处理最短路径：对每个初始位置，BFS 计算到所有格子的最短步数
2. 构建二分图：边权为对应初始位置到目标位置的步数负值
3. KM 算法：求解最小权匹配（通过最大权匹配转化）

代码实现

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

int n, m, K, a, b;
int d[8][4] = {
    {1, 0, 0, 1}, {1, 0, 0, -1}, {-1, 0, 0, 1}, {-1, 0, 0, -1},
    {0, 1, 1, 0}, {0, 1, -1, 0}, {0, -1, 1, 0}, {0, -1, -1, 0}
};
char mp[N][N];
int dis[N][N];

struct node {
    int x, y;
} A[N], B[N];

queue<node> q;
int e[N][N];  // 二分图边权

// 添加边：初始位置i到目标位置j的步数（取负）
void AddEdge(int x, int y, int z) {
    e[x][y] = -z;
}

// BFS计算从初始位置s到所有格子的最短步数
void bfs(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[A[s].x][A[s].y] = 0;
    q.push({A[s].x, A[s].y});
    
    while (!q.empty()) {
        node u = q.front();
        q.pop();
        int x = u.x, y = u.y;
        
        // 尝试8个移动方向
        for (int i = 0; i < 8; ++i) {
            int tx = x + d[i][0] * a + d[i][1] * b;
            int ty = y + d[i][2] * a + d[i][3] * b;
            
            if (1 <= tx && tx <= n && 1 <= ty && ty <= m && 
                mp[tx][ty] != '*' && dis[tx][ty] > 1e9) {
                dis[tx][ty] = dis[x][y] + 1;
                q.push({tx, ty});
            }
        }
    }
    
    // 构建二分图边
    for (int i = 1; i <= K; ++i)
        AddEdge(s, i, dis[B[i].x][B[i].y]);
}

namespace KM {
    // KM算法相关变量
    long long lx[N], ly[N], px[N], py[N], vx[N], vy[N], slack[N], pre[N];
    
    // 扩展增广路径
    void expand(int x) {
        for (int y = px[pre[x]]; x; x = y, y = px[pre[x]])
            py[x] = pre[x], px[pre[x]] = x;
    }
    
    // 处理一个起点
    void deal(int x) {
        queue<int> q;
        q.push(x);
        memset(vx, 0, sizeof(vx));
        memset(vy, 0, sizeof(vy));
        memset(slack, 0x3f, sizeof(slack));
        
        while (true) {
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                vx[x] = 1;
                
                for (int y = 1; y <= K; ++y) {
                    if (!vy[y] && slack[y] > lx[x] + ly[y] - e[x][y]) {
                        slack[y] = lx[x] + ly[y] - e[x][y];
                        pre[y] = x;
                        
                        if (!slack[y]) {
                            vy[y] = 1;
                            if (!py[y]) return expand(y);
                            q.push(py[y]);
                        }
                    }
                }
            }
            
            // 调整顶标
            long long mn = 1e18;
            for (int i = 1; i <= K; ++i)
                if (!vy[i]) mn = min(mn, slack[i]);
            
            for (int i = 1; i <= K; ++i) {
                if (vx[i]) lx[i] -= mn;
                if (vy[i]) ly[i] += mn;
                else slack[i] -= mn;
            }
            
            for (int i = 1; i <= K; ++i) {
                if (!vy[i] && !slack[i]) {
                    vy[i] = 1;
                    if (!py[i]) return expand(i);
                    q.push(py[i]);
                }
            }
        }
    }
    
    // KM算法主函数
    void solve() {
        memset(lx, 0xcf, sizeof(lx));
        
        // 初始化顶标
        for (int x = 1; x <= K; ++x)
            for (int y = 1; y <= K; ++y)
                lx[x] = max(lx[x], (long long)e[x][y]);
        
        // 对每个点进行匹配
        for (int i = 1; i <= K; ++i)
            deal(i);
        
        // 计算总步数
        long long ans = 0;
        for (int i = 1; i <= K; ++i)
            ans += e[i][px[i]];
        
        printf("%lld\n", -ans);  // 输出正数步数
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &K, &a, &b);
    
    for (int i = 1; i <= n; ++i)
        scanf("%s", mp[i] + 1);
    
    for (int i = 1; i <= K; ++i)
        scanf("%d%d", &A[i].x, &A[i].y);
    
    for (int i = 1; i <= K; ++i)
        scanf("%d%d", &B[i].x, &B[i].y);
    
    memset(e, 0xcf, sizeof(e));
    
    // 预处理所有初始位置的最短路径
    for (int i = 1; i <= K; ++i)
        bfs(i);
    
    // KM算法求解最小权匹配
    KM::solve();
    
    return 0;
}

关键优化

1. BFS 预处理

• 对每个初始位置单独进行 BFS
• 计算到所有目标位置的最短步数
• 时间复杂度：$O(k \cdot nm)$

2. KM 算法优化

• 使用 Slack 数组优化顶标调整
• 时间复杂度：$O(k^3)$

3. 问题转化技巧

• 将最小权匹配转化为最大权匹配（取负值）
• 利用 KM 算法求解

复杂度分析

• BFS 预处理：$O(k \cdot nm)$
• KM 算法：$O(k^3)$
• 总复杂度：$O(k \cdot nm + k^3)$

对于 $n,m \leq 100$，$k \leq 500$ 的数据规模，该算法能够高效运行。

正确性保证

1. 最短路径正确性：BFS 保证找到的是最短步数
2. 匹配可行性：题目保证有解，因此二分图存在完美匹配
3. 最优性：KM 算法保证找到的是最小权完美匹配

该算法通过巧妙的图论建模，将复杂的多棋子移动问题转化为经典的二分图匹配问题，从而高效求解。