题解：P7463 [CERC2018] The Lord of the Kings
xuyifei0302 · · 题解
读完题，我们看见“特殊点”、“最小代价”、以及那极小的数据范围，可以很轻松地想到是最小斯坦纳树。
先给出最小斯坦纳树的板子的转移：
for (int i = 0; i < k; i ++) {
int x, y;
cin >> x >> y;
dp[point(x, y)][1 << i] = 0;
}
for (int i = 0; i < (1 << k); i ++) {
for (int j = 1; j <= n * m; j ++) {
for (int k1 = i; k1 >= 0; k1 --) {
if ((i | k1) == i) {
dp[j][i] = min(dp[j][i], dp[j][k1] + dp[j][i - k1]);
}
}
if (dp[j][i] < INF) {
pq.push({j, dp[j][i]});
}
}
dj(i);
}难点在于建图，我们要按照每一种棋子的运动方式建图，模拟即可。
-
对于皇后，我们对于某一个格子斜方向所能到达的所有格子都建一条边，竖直方向所能到达的所有格子都建一条边，水平方向所能到达的所有格子都建一条边。
-
对于车，我们对于竖直方向所能到达的所有格子都建一条边，水平方向所能到达的所有格子都建一条边。
-
对于相，我们对于某一个格子斜方向所能到达的所有格子都建一条边。
-
对于马，我们对于某一个格子马的所有运动方向所能到达的所有格子都建一条边。
但细节很多，详见代码。
下面是代码环节：
using namespace std;
const int INF = 1e9;
struct Node {
int u, dis;
Node (int u_, int dis_) {
u = u_, dis = dis_;
}
};
bool operator < (Node x, Node y) {
return x.dis > y.dis;
}
int n, m, X, Y, k, dp[400][(1 << 10)];
char ch;
vector<int> v[400];
priority_queue<Node> pq;
int point(int x, int y) {
return (x - 1) * m + y;
}
void dj(int s) {
while (!pq.empty()) {
int u = pq.top().u, dis = pq.top().dis;
pq.pop();
if (dp[u][s] < dis) {
continue;
}
for (auto i : v[u]) {
if (dp[i][s] > dp[u][s] + 1) {
dp[i][s] = dp[u][s] + 1;
pq.push({i, dp[i][s]});
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> X >> Y >> ch >> k;
// cout << "Ok\n";
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
// cout << i << " " << j << "k\n";
if (ch == 'N') {
if (i > 1 && j > 2) {
v[point(i, j)].push_back(point(i - 1, j - 2));
}
if (i > 1 && j + 1 < m) {
v[point(i, j)].push_back(point(i - 1, j + 2));
}
if (i < n && j > 2) {
v[point(i, j)].push_back(point(i + 1, j - 2));
}
if (i < n && j + 1 < m) {
v[point(i, j)].push_back(point(i + 1, j + 2));
}
if (j > 1 && i > 2) {
v[point(i, j)].push_back(point(i - 2, j - 1));
}
if (j > 1 && i + 1 < n) {
v[point(i, j)].push_back(point(i + 2, j - 1));
}
if (j < m && i > 2) {
v[point(i, j)].push_back(point(i - 2, j + 1));
}
if (j < m && i + 1 < n) {
v[point(i, j)].push_back(point(i + 2, j + 1));
}
} else if (ch == 'K') {
if (i > 1) {
v[point(i, j)].push_back(point(i - 1, j));
}
if (j > 1) {
v[point(i, j)].push_back(point(i, j - 1));
}
if (i < n) {
v[point(i, j)].push_back(point(i + 1, j));
}
if (j < m) {
v[point(i, j)].push_back(point(i, j + 1));
}
if (i > 1 && j > 1) {
v[point(i, j)].push_back(point(i - 1, j - 1));
}
if (i > 1 && j < m) {
v[point(i, j)].push_back(point(i - 1, j + 1));
}
if (i < n && j > 1) {
v[point(i, j)].push_back(point(i + 1, j - 1));
}
if (i < n && j < m) {
v[point(i, j)].push_back(point(i + 1, j + 1));
}
} else if (ch == 'R') {
for (int k1 = 1; k1 <= n; k1 ++) {
if (k1 != i) {
v[point(i, j)].push_back(point(k1, j));
}
}
for (int k1 = 1; k1 <= m; k1 ++) {
if (k1 != j) {
v[point(i, j)].push_back(point(i, k1));
}
}
} else if (ch == 'B') {
for (int xx = i - 1, yy = j - 1; xx && yy; xx --, yy --) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i - 1, yy = j + 1; xx && yy <= m; xx --, yy ++) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i + 1, yy = j - 1; xx <= n && yy; xx ++, yy --) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i + 1, yy = j + 1; xx <= n && yy <= m; xx ++, yy ++) {
v[point(i, j)].push_back(point(xx, yy));
}
} else if (ch == 'Q') {
for (int k1 = 1; k1 <= n; k1 ++) {
if (k1 != i) {
v[point(i, j)].push_back(point(k1, j));
}
}
for (int k1 = 1; k1 <= m; k1 ++) {
if (k1 != j) {
v[point(i, j)].push_back(point(i, k1));
}
}
for (int xx = i - 1, yy = j - 1; xx && yy; xx --, yy --) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i - 1, yy = j + 1; xx && yy <= m; xx --, yy ++) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i + 1, yy = j - 1; xx <= n && yy; xx ++, yy --) {
v[point(i, j)].push_back(point(xx, yy));
}
for (int xx = i + 1, yy = j + 1; xx <= n && yy <= m; xx ++, yy ++) {
v[point(i, j)].push_back(point(xx, yy));
}
}
}
}
// cout << "ok\n";
for (int i = 1; i <= n * m; i ++) {
for (int j = 0; j < (1 << k); j ++) {
dp[i][j] = INF;
}
}
// cout << "Ok";
// for (int i = 1; i <= n * m; i ++) {
// for (int j = 0; j < (1 << k); j ++) {
// cout << dp[i][j] << " ";
// }
// cout << "\n";
// }
if (dp[point(X, Y)][(1 << k) - 1] == INF) {
cout << "-1";
} else {
cout << dp[point(X, Y)][(1 << k) - 1];
}
return 0;
}
/*
3 3
3 1 K
2
1 1
1 3
1000000000 0 2 2
1000000000 1 1 2
1000000000 2 0 2
1000000000 1 2 3
1000000000 1 1 2
1000000000 2 1 3
1000000000 2 2 3
1000000000 2 2 3
1000000000 2 2 3
15 15 4 13 K 10 12 7 10 14 1 10 6 3 8 3 11 9 14 13 3 2 6 11 7 11
*/