洛谷/USACO 亚瑟王的宫殿 Camelot

这道题,参考罗进瑶同学的题解写了好半天,改了好半天……在此衷心的感谢!
洛谷题号:P1930

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
int ans = 2e9;//answer
int r, c, sn = 0;//r,c,soilder_number
int kx, ky;//king_pos(x,y)
int sposx[1050], sposy[1050];//soilder_pos(x,y)
int dis[30][45][30][45];//dis[x1][y1][x2][y2] the distance from (x1,y1) to (x2,y2)
bool visited[30][45];
int bfs_x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int bfs_y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int min_kdis[5][5] = {
    { 2, 2, 2, 2, 2 },
    { 2, 1, 1, 1, 2 },
    { 2, 1, 0, 1, 2 },
    { 2, 1, 1, 1, 2 },
    { 2, 2, 2, 2, 2 }
};
#define bfsxp (cur.x + bfs_x[i])
#define bfsyp (cur.y + bfs_y[i])
struct point{
    int x, y, time;
    point(){}
    point(int x, int y, int time){
        this->x = x;
        this->y = y;
        this->time = time;
    }
};
void bfs(int x, int y){
    memset(visited, false, sizeof(visited));
    queue<point> q;
    q.push(point(x, y, 0));
    while (!q.empty()){
        point cur = q.front(); q.pop();
        if (visited[cur.x][cur.y])continue;
        visited[cur.x][cur.y] = true;
        dis[x][y][cur.x][cur.y] = cur.time;
        for (int i = 0; i <= 7; i++){
            if (bfsxp > 0 && bfsxp <= c&&bfsyp > 0 && bfsyp <= r&&!visited[bfsxp][bfsyp]){
                q.push(point(bfsxp, bfsyp, cur.time + 1));
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    memset(dis, 0x7f, sizeof(dis));
    cin >> r >> c;
    char ct; int t;
    cin >> ct >> t;
    kx = ct - 'A' + 1; ky = t;
    while (cin >> ct >> t){
        sposx[++sn] = ct - 'A' + 1;
        sposy[sn] = t;
        bfs(sposx[sn], sposy[sn]);
    }
    if (sn == 0){
        cout << 0 << endl;
        return 0;
    }
    for (int i = -2; i <= 2; i++){
        for (int j = -2; j <= 2; j++){
            if (kx + i > 0 && kx + i <= c&&ky + j > 0 && ky + j <= r)bfs(kx + i, ky + j);
        }
    }
    for (int i = 1; i <= c; i++){
        for (int j = 1; j <= r; j++){ //选取集中点
            int s_sum = 0;
            for (int s = 1; s <= sn; s++){ //进行棋子的试探
                if (dis[sposx[s]][sposy[s]][i][j] > 1e6){
                    s_sum = 1e8;
                    break;
                }
                else s_sum += dis[sposx[s]][sposy[s]][i][j];
            }
            if (s_sum == 1e8)continue;
            for (int x = -2; x <= 2; x++){
                for (int y = -2; y <= 2; y++){
                    int nx = kx + x, ny = ky + y;
                    int k = min_kdis[x + 2][y + 2];
                    if (nx > 0 && nx <= c&&ny > 0 && ny <= r){
                        for (int s = 1; s <= sn; s++){
                            int re = s_sum - dis[sposx[s]][sposy[s]][i][j] + dis[sposx[s]][sposy[s]][nx][ny] + k + dis[nx][ny][i][j];
                            if (re > 0)ans = min(ans, re);
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

我研究了好半天,还是有两个地方不是特别明白,希望罗同学能给予解答:
1、第87行,int k处,这里是求“国王到(骑士接国王的位置)的最短距离”,您说“当在国王的对角线上能到达的时候距离是abs(kx-newn)否则是两个坐标之差的和”,我觉得好像是不对的。假设国王的坐标是(0,0),骑士的位置是(2,1),按照您的理解,距离应为2+1=3;而我觉得国王可以从(0,0)沿对角线到(1,1),再沿直线到(2,1)。这样只需要两步,所以我在程序中做的处理是开了一个min_kdis数组,手动打出环绕在国王旁边+-2以内的距离,然后进行查表。这样的结果,在洛谷和USACO中测试时都能AC。所以您看看我的做法是否是正确的呢?
2、一开始的第90至91行,我是这么写的:
$$ans = min(ans, s_sum – dis[sposx[s]][sposy[s]][i][j] + dis[sposx[s]][sposy[s]][nx][ny] + k + dis[nx][ny][i][j]);$$
和您的做法一样,但是这样我发现洛谷的第八个点过不去,会出现负数。经过我的推测,应该是骑士s到骑士/国王汇合点的路径不存在导致的。所以我就过滤掉了负数,A掉了这道题目。但是您的题解中并没有过滤掉负数,能否麻烦您帮我看一下我的代码中是否有哪里存在问题,或者讲述一下您的代码为什么不用过滤/不会出现这种情况?
多谢罗进瑶同学!您可以私信/QQ/在博客下方评论都可以,多谢!

发表评论

电子邮件地址不会被公开。 必填项已用*标注