[USACO3.3] 亚瑟王的宫殿

#include <bits/stdc++.h>
using namespace std;
int r, c;
int kingX, kingY;
int tot;                                        // 骑士数量
int knightX[40 * 26 + 5], knightY[40 * 26 + 5]; // 骑士坐标
// 任意两点间骑士最短路
int dis[40 + 5][26 + 5][40 + 5][26 + 5];
queue<pair<int, int>> q;
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};
void bfs(int x, int y)
{
    // 数组初始化
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            dis[x][y][i][j] = -1;
    // 起点入队
    q.push(make_pair(x, y));
    dis[x][y][x][y] = 0;
    // 广搜
    while (!q.empty())
    {
        pair<int, int> now = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int nx = now.first + dx[i];
            int ny = now.second + dy[i];
            if (1 <= nx && nx <= r &&
                1 <= ny && ny <= c &&
                dis[x][y][nx][ny] == -1)
            {
                dis[x][y][nx][ny] = dis[x][y][now.first][now.second] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> r >> c;
    char tempC;
    int temp;
    cin >> tempC >> temp;
    kingY = tempC - 'A' + 1;
    kingX = temp;
    while (cin >> tempC >> temp)
    {
        tot++;
        knightY[tot] = tempC - 'A' + 1;
        knightX[tot] = temp;
    }
    // 计算每个点到其它点的距离
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            bfs(i, j);
    // 枚举
    int ans = 1000000000;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
        {
            // 在 (i,j) 会合
            // 方案 1，所有人和王自己去
            bool flag = true; // 是否所有骑士都能到
            int len1 = 0;     // 所有骑士到汇合点的路程
            for (int id = 1; id <= tot; id++)
            {
                if (dis[knightX[id]][knightY[id]][i][j] == -1)
                {
                    flag = false;
                    break;
                }
                len1 += dis[knightX[id]][knightY[id]][i][j];
            }
            if (!flag)
                continue;
            // 王到汇合点的路程
            int len2 = abs(kingX - i) + abs(kingY - j);
            ans = min(ans, len1 + len2);
            // 方案 2，找个骑士去接王
            int xl = max(kingX - 2, 1), xr = min(kingX + 2, r);
            int yl = max(kingY - 2, 1), yr = min(kingY + 2, c);
            for (int x = xl; x <= xr; x++)
                for (int y = yl; y <= yr; y++)
                {
                    // 检查 x,y 能不能到 i,j
                    if (dis[x][y][i][j] == -1)
                        continue;
                    // 在 (x,y) 位置接王
                    // 枚举哪个骑士接
                    for (int id = 1; id <= tot; id++)
                    {
                        // 检查这个骑士能不能到 (x,y)
                        if (dis[knightX[id]][knightY[id]][x][y] == -1)
                            continue;
                        int now = 0;
                        // len1 去掉第 id 个骑士的贡献
                        now += len1 - dis[knightX[id]][knightY[id]][i][j];
                        // 第 id 个骑士和王去接王点
                        now += dis[knightX[id]][knightY[id]][x][y];
                        now += abs(kingX - x) + abs(kingY - y);
                        // 从接王点骑士去汇合点
                        now += dis[x][y][i][j];
                        // 尝试更新答案
                        ans = min(ans, now);
                    }
                }
        }
    cout << ans;
    return 0;
}