拯救大兵瑞恩
原题链接
题目描述
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形，其南北方向被划分为 N 行，东西方向被划分为 M 列， 于是整个迷宫被划分为 N×M 个单元。
每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
注意： 门可以从两个方向穿过，即可以看成一条无向边。
迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 P 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即 (N,M) 单元里，并已经昏迷。
迷宫只有一个入口，在西北角。
也就是说，麦克可以直接进入 (1,1) 单元。
另外，麦克从一个单元移动到另一个相邻单元的时间为 1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。
思路 状态压缩+双端队列BFS
动态规划可以看成特殊的最短路问题。因为动态规划所求的路径，在最短路内是拓扑序的。因此在做最短路的问题时，可以先用动态规划的思想，然后转化为最短路求解。
状态压缩DP
关于建图
对于 \([x,y]\) 向其他点位连边是很麻烦的。可以将 \([x,y]\) 压缩成一维状态，用一维数字代表点位。即 \([x,y]=x+(y-1)*x\)
存储钥匙
对于每个点，用key数组存储所包含的钥匙。其中下标是一维状态，即 关于建图 内的方法。
存储钥匙，可以用二进制压缩，二进制的每一位代表第 \(i\) 类的钥匙是否存在。
双端队列BFS
根据状态压缩DP的状态计算
使用双端队列BFS可以达到 \(O(n)\) 的时间复杂度。
代码
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 | #include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 11, M = 400, P = 1 << N;
int n, m, p, k;
int h[N * N], e[M], w[M], ne[M], idx;
int dist[N * N][P], key[N * N], g[N][N];
bool st[N * N][P];
set<PII> edges;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build() {
int dx[] = {1, -1, 0, 0};
int dy[] ={0, 0, 1, -1};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int u = 0; u < 4; u++) {
int x = i + dx[u], y = j + dy[u];
if (x < 1 || x > n || y < 1 || y > m) continue;
int a = g[i][j], b = g[x][y];
// 如果存在 a->b 的边，continue。否则连边
if (edges.count({a, b})) continue;
add(a, b, 0);
}
}
int bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0;
deque<PII> q;
q.push_back({1, 0});
while (!q.empty()) {
auto [ver, state] = q.front();
q.pop_front();
if (st[ver][state]) continue;
st[ver][state] = true;
// 第一次到终点，返回答案，因为bfs保证找到的第一次到达的是最短路
if (ver == n * m) return dist[ver][state];
// 当前格子存在钥匙
if (key[ver]) {
int new_state = state | key[ver];
if (dist[ver][new_state] > dist[ver][state]) {
dist[ver][new_state] = dist[ver][state];
q.push_front({ver, new_state});
}
}
// 向周围点转移
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (w[i] && !(state >> w[i] - 1 & 1)) continue; // 有门，无匹配钥匙
if (dist[j][state] > dist[ver][state] + 1) {
dist[j][state] = dist[ver][state] + 1;
q.push_back({j, state});
}
}
}
return -1; // 找不到答案
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> p >> k;
// 将二维的点映射到一维状态
for (int i = 1, t = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
g[i][j] = t++;
// door and wall
while (k--) {
int x1, y1, x2, y2, z;
cin >> x1 >> y1 >> x2 >> y2 >> z;
int a = g[x1][y1], b = g[x2][y2];
edges.insert({a, b});
edges.insert({b, a});
if (z) { // 有门，连边
add(a, b, z);
add(b, a, z);
}
}
build(); // 没有门和墙之间的格子连边
// key
cin >> k;
while (k--) {
int x, y, z;
cin >> x >> y >> z;
int t = g[x][y];
key[t] |= 1 << z - 1; // 可能存在多个钥匙在一个格子内
}
cout << bfs() << endl;
return 0;
}
|