P1930 [USACO3.3] 亚瑟王的宫殿

· · 题解

这篇题解里有这样一段话：

  1. 那这题是不是没做头了？

题当然还是可以做，你可以枚举棋盘上每一个点来判断是否为王与骑士相遇点，然后暴力枚举骑士，再暴力枚举集合点，最劣是 O(R^3*C^3) ，但是不可能达到这么大。

但是实际上没有 R \times C 这么多点（但是 5 \times 5 和 7 \times 7 很明显不够）。

先考虑对角线的情况，图中红点是国王，黄点是骑士，绿色箭头是骑士的移动路线。

这段路线骑士走会产生 4 的代价，但国王走只有 3 的代价，由此可以得出上车点在对角线上时只能让国王走到上车点。

手玩一下这幅图（也可以写暴力来验证），可以得出结论：如果上车点在黄色点上，那么就一定会让国王走到上车点。

所以只需要把 5 \times 5 的题解复制借鉴一下，把贪心范围加上国王所处的两条对角线就可以了。

最后时间复杂度为 O((R + C) \times R^2 \times C^2)，可以通过本题。

Code

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

#define int long long

struct node {
    int x, y;
    int d;
} pe[2010];

int r, c, dx[] = {1, 2, 2, 1, -1, -2, -2, -1},  dy[] = {2, 1, -1, -2, -2, -1, 1, 2}, cnt;
bool v[50][30];
int ans = 1145141919810ll, d[50][30][50][30];

void bfs(int a, int b) {
    queue<node> q;
    q.push({a, b, 0});
    v[a][b] = 1;
    d[a][b][a][b] = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y;
        d[a][b][x][y] = q.front().d;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && !v[nx][ny]) {
                v[nx][ny] = 1;
                q.push({nx, ny, d[a][b][x][y] + 1});
            }
        }
    }
}

signed main() {
    cin >> r >> c;
    for (int i = 0; i <= r + 1; i++) {
        for (int j = 0; j <= c + 1; j++) {
            for (int a = 0; a <= r + 1; a++) {
                for (int b = 0; b <= c + 1; b++) {
                    d[i][j][a][b] = 2e8;
                }
            }
        }
    }
    char t1;
    int t2;
    while (cin >> t1 >> t2) {
        pe[cnt].x = t2;
        pe[cnt].y = t1 - 'A' + 1;
        cnt++;
    }
    cnt--;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            memset(v, 0, sizeof(v));
            bfs(i, j);
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            int g = 0;
            for (int k = 1; k <= cnt; k++) {
                g += d[pe[k].x][pe[k].y][i][j];
            }
            ans = min(g + max(abs(pe[0].x - i), abs(pe[0].y - j)), ans);
            for (int k = 1; k <= cnt; k++) {
                int temp = g - d[pe[k].x][pe[k].y][i][j];
                for (int a = max(1ll, pe[0].x - 2); a <= min(r, pe[0].x + 2); a++) {
                    for (int b = max(1ll, pe[0].y - 2); b <= min(c, pe[0].y + 2); b++) {
                        ans = min(temp + d[pe[k].x][pe[k].y][a][b] + max(abs(a - pe[0].x), abs(b - pe[0].y)) + d[a][b][i][j], ans);
                    }
                }
                int a = pe[0].x, b = pe[0].y;
                while (a > 0 && b > 0) {
                    a--;
                    b--;
                    ans = min(temp + d[pe[k].x][pe[k].y][a][b] + max(abs(a - pe[0].x), abs(b - pe[0].y)) + d[a][b][i][j], ans);
                }
                a = pe[0].x, b = pe[0].y;
                while (a > 0 && b <= c) {
                    a--;
                    b++;
                    ans = min(temp + d[pe[k].x][pe[k].y][a][b] + max(abs(a - pe[0].x), abs(b - pe[0].y)) + d[a][b][i][j], ans);
                }
                a = pe[0].x, b = pe[0].y;
                while (a <= r && b > 0) {
                    a++;
                    b--;
                    ans = min(temp + d[pe[k].x][pe[k].y][a][b] + max(abs(a - pe[0].x), abs(b - pe[0].y)) + d[a][b][i][j], ans);
                }
                a = pe[0].x, b = pe[0].y;
                while (a <= r && b <= c) {
                    a++;
                    b++;
                    ans = min(temp + d[pe[k].x][pe[k].y][a][b] + max(abs(a - pe[0].x), abs(b - pe[0].y)) + d[a][b][i][j], ans);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}