自动搬运

查看原文

来自洛谷，原作者为

	P2441M 却仍愿/坚信着/世间最美好的一切/正御风漂泊

搬运于2025-08-24 23:17:25，当前版本为作者最后更新于2025-06-01 18:11:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\text{Upd 2025/6/3}$：修改了一些笔误。

题意

有一个 $n\times m$ 的地图，其中 . 表示空地，# 表示墙，X 表示起点，W 表示终点。你可以从空地 $(i,j)$ 走一步到上/下/左/右的空地，也可以使用一次魔法，从空地 $(i,j)$ 走到左上/左下/右上/右下的空地而不耗费步数。从起点走到终点，你需要在最小化步数的前提下最小化使用魔法的次数，或报告无解。$2\leq n,m\leq 5\times 10^3$。

题解

用状态 $(x,y,t_1,t_2)$ 表示走到 $(x,y)$ 处耗费了 $t_1$ 步，使用了 $t_2$ 次魔法。容易想到用以 $t_1$ 为第一关键字、$t_2$ 为第二关键字的小优先队列维护最优状态，然后跑 BFS。这样子时间复杂度是 $\mathcal{O}(nm\log{(nm)})$ 的，可以获得 $75$ 分。

考虑优化。我们发现每次状态转移时，要么给 $t_1$ 加 $1$，要么给 $t_2$ 加 $1$，考虑 0/1 BFS，也就是用双端队列替代优先队列。最直接的想法就是给 $t_1$ 加 $1$ 的状态加到队尾，给 $t_2$ 加 $1$ 的状态加到队头。由于每次取出的状态是单增的，不难证明其正确性。

但我们一写，发现它 WA 了。

问题在哪儿？我们发现队列中的状态是不严格单调递增的，取出最优状态 $(x,y,t_1,t_2)$ 后，队头可能还有 $(x',y',t_1,t_2)$ 的状态，如果我们此时就把 $(x,y,t_1,t_2+1)$ 加到队头，单调性就被破坏了。

所以我们每次把 $t_1$ 和 $t_2$ 都相同的状态全部取出，然后再加入所有新的状态即可。

时间复杂度 $\mathcal{O}(nm)$。

代码

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e3 + 5;
const int dx1[] = {-1, 1, 0, 0}, dy1[] = {0, 0, -1, 1};
const int dx2[] = {-1, -1, 1, 1}, dy2[] = {-1, 1, -1, 1};

int n, m, x1, y1, x2, y2;
char a[N][N];
bool vis[N][N];
struct Node {
	int x, y, t1, t2;
	bool operator<(const Node &x) const {
		if (t1 != x.t1) return t1 > x.t1;
		return t2 > x.t2;
	}
};
deque<Node> q;
vector<Node> v1, v2;

inline void calc() {
	q.push_front({x1, y1, 0, 0});
	while (!q.empty()) {
		Node cur = q.front();
		while (!q.empty() && cur.t1 == q.front().t1 && cur.t2 == q.front().t2) {
			cur = q.front(); q.pop_front();
			if (cur.x == x2 && cur.y == y2) { cout << cur.t1 << ' ' << cur.t2 << '\n'; return; }
			if (vis[cur.x][cur.y]) continue;
			vis[cur.x][cur.y] = 1;
			for (int i = 0; i < 4; ++i) {
				int x = cur.x + dx1[i], y = cur.y + dy1[i];
				if (!x || !y || x == n + 1 || y == m + 1 || a[x][y] == '#') continue;
				v1.push_back({x, y, cur.t1 + 1, cur.t2});
			}
			for (int i = 0; i < 4; ++i) {
				int x = cur.x + dx2[i], y = cur.y + dy2[i];
				if (!x || !y || x == n + 1 || y == m + 1 || a[x][y] == '#') continue;
				v2.push_back({x, y, cur.t1, cur.t2 + 1});
			}
		}
		for (Node st : v2) q.push_front(st);
		for (Node st : v1) q.push_back(st);
		v1.clear(), v2.clear();
	}
	cout << "-1 -1\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
    	cin >> a[i] + 1;
    	for (int j = 1; j <= m; ++j)
    		if (a[i][j] == 'X') x1 = i, y1 = j;
    		else if (a[i][j] == 'W') x2 = i, y2 = j;
    }
    calc();
    return 0;
}