这道题，参考罗进瑶同学的题解写了好半天，改了好半天……在此衷心的感谢！
洛谷题号：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/在博客下方评论都可以，多谢！