luogu-HXOI U330374-密室逃脱

Horean0574 rp++

原题链接

Algorithms: 搜索 广搜,BFS


依照题意,不难发现这是一道很普通的广搜题,只不过是三维广搜。对于这种情况我们只需要添加 dxdy 数组的值且再添加一个 dz 数组,值如下。

1
2
3
dz[6] = {-1, 1, 0, 0, 0, 0};
dx[6] = {0, 0, -1, 0, 1, 0};
dy[6] = {0, 0, 0, 1, 0, -1};

在此题中,我们发现除了正常广搜之外,还有两个要点:

  1. 小H 拥有一些体力值,某些时候会需要消耗体力拆卸陷阱;
  2. 小H 手上的钥匙数量会变化,且可能会有需要钥匙开门的时候。

虽然题面看上去很复杂,但我们只需要仔细分析,其实可以发现:

  • 当 小H 有足够的体力时,那么必须拆卸陷阱,否则不将当前状态入队。
  • 当 小H 受伤有足够的钥匙时,那么必须开门,否则不降当前状态入队。

这样一来,我们广搜中也只是多了两个 分支结构

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
#include <iostream>
#include <queue>

#define endl '\n'

using namespace std;

struct Node {
int z, x, y, t, k, v;
};

const int H = 165;
const int N = 405;

int h, n, m, v, w;
int a[H][N][N], sz, sx, sy;
queue<Node> q;
bool inq[H][N][N];
int dz[6]{-1, 1, 0, 0, 0, 0}, dx[6]{0, 0, -1, 0, 1, 0}, dy[6]{0, 0, 0, 1, 0, -1};

int bfs() {
int k = a[sz][sx][sy] == 5 ? 1 : 0;
q.push({sz, sx, sy, 0, k, v});
inq[sz][sx][sy] = true;
Node p;

while (q.size()) {
p = q.front();
q.pop();

for (int i = 0; i < 6; ++i) {
int nz = p.z + dz[i];
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int nt = p.t + 1;
int nk = p.k;
int nv = p.v;

if (nz < 1 || nz > h) continue;
if (nx < 1 || nx > n || ny < 1 || ny > m) {
return nt;
}
if (inq[nz][nx][ny]) continue;
if (a[nz][nx][ny] == 2) continue;
if (a[nz][nx][ny] == 3) {
if (nv >= w) {
nv -= w;
} else {
continue;
}
} else if (a[nz][nx][ny] == 4) {
if (nk) {
--nk;
} else {
continue;
}
} else if (a[nz][nx][ny] == 5) {
++nk;
}

q.push({nz, nx, ny, nt, nk, nv});
inq[nz][nx][ny] = true;
}
}

return 0;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);

cin >> h >> n >> m;
cin >> sz >> sx >> sy;
cin >> v >> w;
for (int k = 1; k <= h; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[k][i][j];
}
}
}

int ans = bfs();
if (!ans) {
cout << "No";
} else {
cout << "Yes" << endl;
cout << ans;
}
}
  • Title: luogu-HXOI U330374-密室逃脱
  • Author: Horean0574
  • Created at : 2023-08-23 08:19:24
  • Updated at : 2023-09-01 19:52:20
  • Link: https://blog.hxrch.top/2023/08/23/luogu-HXOI-U330374-密室逃脱/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
luogu-HXOI U330374-密室逃脱