Luogu P1979 [NOIP 2013] 华容道

qwq

70分的暴力很好想,棋子移到空白,等价于空白与棋子交换位置,直到移动到起点的位置,BFS乱跑就完事。

考虑优化,70 分算法的瓶颈在于空白有太多无用的移动。考虑空白移动的本质,是让起点棋子借助空白在棋盘上运动。一个棋子想要移动到另一个棋子,需要空白从一个棋子的旁边移动到另一个棋子。于是可以发现有效的状态可以看作三元组 (x, y, dir),表示 (x, y) 的棋子向 dir 方向移动 (dir对应一个方向数组)。对于每个棋子,跑一遍 bfs,处理出它到所有可达棋子的距离,如果它旁边的棋子可达,就连边。最后再从起点开始跑spfa(稀疏图)。就过了。

这道题和其他建图跑最短路的题很相似,但状态的设计很巧妙。关键在于提取出有效的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>

const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m, q, matrix[35][35], d[35][35], dis[114514];
int ex, ey, sx, sy, tx, ty;
bool vis[114514];
std::vector<std::pair<int, int>> g[114514];

inline int read() {
int a = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a;
}

inline int hash(int x, int y, int d) { return x * 120 + y * 4 + d; }

void bfs(int k) {
memset(d, -1, sizeof(d));
std::queue<std::pair<int, int>> q;
matrix[sx][sy] = d[ex][ey] = 0;
q.push({ex, ey});
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i <= 3; ++i) {
int xx = x + dx[i], yy = y + dy[i];
if (d[xx][yy] != -1 || !matrix[xx][yy]) continue;
d[xx][yy] = d[x][y] + 1;
q.push({xx, yy});
}
}
matrix[sx][sy] = 1;
if (k == 4) return;
for (int i = 0; i <= 3; ++i) {
int xx = sx + dx[i], yy = sy + dy[i];
if (d[xx][yy] == -1) continue;
g[hash(sx, sy, k)].push_back({hash(sx, sy, i), d[xx][yy]});
}
g[hash(sx, sy, k)].push_back({hash(ex, ey, (k + 2) % 4), 1});
}

void spfa() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
std::queue<int> q;
for (int k = 0; k <= 3; ++k) {
int xx = sx + dx[k], yy = sy + dy[k];
int id = hash(sx, sy, k);
if (d[xx][yy] != -1) dis[id] = d[xx][yy], q.push(id), vis[id] = true;
}
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = false;
for (auto t : g[x]) {
int y = t.first, w = t.second;
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if (!vis[y]) q.push(y), vis[y] = true;
}
}
}
}

signed main() {
n = read(), m = read(), q = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) matrix[i][j] = read();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!matrix[i][j]) continue;
for (int k = 0; k <= 3; ++k) {
sx = i, sy = j, ex = sx + dx[k], ey = sy + dy[k];
if (matrix[ex][ey]) bfs(k);
}
}
}
while (q--) {
ex = read(), ey = read();
sx = read(), sy = read();
tx = read(), ty = read();
if (sx == tx && sy == ty) {
puts("0");
continue;
}
bfs(4), spfa();
int ans = 0x3f3f3f3f;
for (int k = 0; k <= 3; ++k)
ans = std::min(ans, dis[hash(tx, ty, k)]);
if (ans == 0x3f3f3f3f) puts("-1");
else printf("%d\n", ans);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×