算法:SPFA + 枚举
时间复杂度:$O(R^2 \times C^2)$
相信你第一遍听是比较懵懂的,这篇题解会让你把思路梳理的更加清楚,It’s Show time。
首先,你要清楚,最终的汇聚点可能是棋盘上的任意一点,那么,我们把棋盘的每个点当作一个汇聚点,求解到达该汇聚点的最小步数是不是可以呢?
答案显然是可以的,而这也就是一个简单枚举。
如何求骑士到达棋盘任意一点的最短距离呢?
此时就需要用到单源最短路算法,$spfa$ 或者 $dijkstra$ 算法都行,其中用 $dist\underline{}sum [x][y]$ 表示所有骑士到达 $(x, y)$ 点的最短距离,用 $dist\underline{}min [x][y]$ 表示国王到达 $(x, y)$ 点的最短距离。
$\therefore$ $result_{(x, y)} = dist\underline{}sum [x][y] + dist\underline{}min [x][y]$。
此时的关注点就变成了如何求国王到达汇聚点的最短距离。(骑士可用上述的 $spfa$ 或者 $dijkstra$ 求解)
国王到达汇聚点有三种途径:
$$f(x)=
\begin{cases}
1& \{完全自己走路}\\\
2& \{完全搭载骑士}\\\
3& \{自己走路 + 搭载骑士}
\end{cases}$$
此时第三种方式肯定是最常见的。
可以用一个三位数组 $dist[x][y][2]$ 表示骑士达到 $(x, y)$ 点的 未载国王 和 搭载国王 两类情况,在 $spfa$ 时不断进行更新即可,当然开始要进行初始化(完全自己走路)。
$\therefore$ $dist\underline{}min[x][y] = dist[x][y][1] - dist[x][y][0]$。
这是我觉得十分精妙的地方(多多体会)。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 40, M = N * N, INF = 0x3f3f3f3f;
int n, m;
int dist_sum[N][N], dist_min[N][N], dist[N][N][2];
PII king;
bool st[N][N][2];
struct Node {
int x, y;
int s;
};
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
void spfa(int sx, int sy)
{
queue <Node> q;
memset(dist, 0x3f, sizeof(dist));
dist[sx][sy][0] = 0;
st[sx][sy][0] = true;
q.push({sx, sy, 0});
while (!q.empty()) {
auto t = q.front();
q.pop();
st[t.x][t.y][t.s] = false;
for (int i = 0; i < 8; ++i) {
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 1 || x > n || y < 1 || y > m) {
continue;
}
if (dist[x][y][t.s] > dist[t.x][t.y][t.s] + 1) {
dist[x][y][t.s] = dist[t.x][t.y][t.s] + 1;
if (!st[x][y][t.s]) {
q.push({x, y, t.s});
st[x][y][t.s] = true;
}
}
}
if (!t.s) {
int d = dist[t.x][t.y][t.s] + max(abs(king.x - t.x), abs(king.y - t.y));
if (dist[t.x][t.y][1] > d) {
dist[t.x][t.y][1] = d;
if (!st[t.x][t.y][1]) {
q.push({t.x, t.y, 1});
st[t.x][t.y][1] = true;
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (dist[i][j][0] == INF) {
dist_sum[i][j] = INF;
}
else {
dist_sum[i][j] += dist[i][j][0];
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dist_min[i][j] = min(dist_min[i][j], dist[i][j][1] - dist[i][j][0]);
}
}
}
int main()
{
cin >> n >> m;
int x;
char y;
cin >> y >> x;
y = y - 'A' + 1;
king = {x, y};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dist_min[i][j] = max(abs(i - x), abs(j - y));
}
}
while (cin >> y >> x) {
y = y - 'A' + 1;
spfa(x, y); // spfa 求最短路
}
int res = INF;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
res = min(res, dist_sum[i][j] + dist_min[i][j]);
}
}
cout << res << endl;
return 0;
}
亲,是这样,对吗?
dist_min[x][y]:表示选择一名骑士从起点(sx,sy)出发,去接上国王到达(x, y)的额外走的最小步数
补充一下,spfa的复杂度不是图中点的数量,这题边的数量是点的数量 * (8(8个方向)+ 1(带上国王)),复杂度是O(R^2×C^2 * 9),当然big O表示是不写常数的,但是我们的确要算复杂度是否超1e8.
抄自网上:
SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的,k是一个常数,在稀疏图中小于2)。 但是,SPFA算法稳定性较差,在稠密图中SPFA算法时间复杂度会退化。
好6
爷爷姥姥觉得不错给个赞再走呗,嘻嘻。