自动搬运

查看原文

来自洛谷，原作者为

	xuyifei0302 人谁无过？过而能改，善莫大焉。

搬运于2025-08-24 22:30:06，当前版本为作者最后更新于2025-03-29 15:22:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

读完题，我们看见“特殊点”、“最小代价”、以及那极小的数据范围，可以很轻松地想到是最小斯坦纳树。

先给出最小斯坦纳树的板子的转移：

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
*/