题解：P12684 【MX-J15-T4】叉叉学习魔法
P2441M
·
·
题解
## 题意
有一个 $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)$。
## 代码
```cpp
#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;
}
```