LeetCode LCP 31 - 变换的迷宫

题目链接:LeetCode LCP 31 - 变换的迷宫(LCCUP 21 春季赛第 4 题)

思路

题目表示我们可以使用两个权利各一次:

  • 永久性改变
  • 暂时性改变

也就是说在第 \(i\) 个时刻,如果小力位于 \((x, y)\),此时有四种情况:

  • 未使用「永久性改变」,未使用「暂时性改变」
  • 未使用「永久性改变」,已使用「暂时性改变」
  • 已使用「永久性改变」,未使用「暂时性改变」
  • 已使用「永久性改变」,已使用「暂时性改变」

我们可以用这几个常量来表示这四种情况(与上面一一对应):

1
2
3
4
5
const int
NONE_USED = 0,
ONLY_TEMP = 1,
ONLY_PERM = 2,
TEMP_PERM = 3;

我们可以根据当前时刻 \(i\)、当前坐标 \((x, y)\),以及当前的权利使用情况(即上面四种,记这个量为 \(\rm s\)\(s \in \{ 0, 1, 2, 3 \}\)),这几个量作为状态,来递推结果,方法有点类似「分层图最短路」的思想。

\(f(i, x, y, s)\) 表示从 \(0\) 时刻、\((0, 0)\) 点、未使用任何权利,到当前时刻为 \(i\),在坐标 \((x, y)\),权利使用情况为 \(s\) 的最小时间。

类似于单源最短路径算法,我们把 \(f(0, 0, 0, {\rm NONE\_USED})\) 初始化为 \(0\),剩下的所有状态对应的 \(f\) 设置为 \(+\infty\),然后把二元组 \(((i, x, y, s), f(i, x, y, s))\) 扔进队列,开始做 BFS。在拓展新的状态时:

  • 新状态的 \(i\) 用旧状态的 \(i\)\(1\) 得到,表示从 \(i\) 时刻转移到 \(i + 1\) 时刻
  • 新状态的 \((x', y')\) 用旧状态的 \((x, y)\) 分别叠加这五个增量:
    • \((0, 0)\)
    • \((0, 1)\)
    • \((0, -1)\)
    • \((1, 0)\)
    • \((-1, 0)\)

下面我们来对新状态的 \(s\) 进行讨论。

  • 当地图上 \({\rm mazes}(i, x, y)\).,即可行时,对 \((i, x, y, s)\)\((i + 1, x', y', s)\) 做一次松弛,即如果 \(f(i, x, y, s) + 1 < f(i + 1, x', y', s)\),就令 \(f(i + 1, x', y', s) = f(i, x, y, s) + 1\),然后把二元组 \(((i + 1, x', y', s), f(i + 1, x', y', s))\) 加入队列。
  • 当地图上 \({\rm mazes}(i, x, y)\)#,即不可行时,要对 \(s\) 进行分类:
    • 如果 \(s = {\rm ONLY\_TEMP}\),即未使用「永久性改变」,已使用「暂时性改变」,我们需要使用一次「永久性改变」来「打通」这个位置,那么 \(s\) 将由 \({\rm ONLY\_TEMP}\) 变成 \({\rm TEMP\_PERM}\),即我们要在 \((i, x, y, s)\)\((i + 1, x', y', {\rm TEMP\_PERM})\) 之间做一次松弛
    • 如果 \(s = {\rm ONLY\_PERM}\),这个时候要判断是对哪个点使用了「永久性改变」
      • 如果正好是当前 \((x', y')\),那么我们可以直接松弛 \((i, x, y, s)\)\((i + 1, x', y', s)\)
      • 如果并不是当前 \((x', y')\),我们需要使用一次「临时性改变」,即需要松弛 \((i, x, y, s)\)\((i + 1, x', y', {\rm TEMP\_PERM})\)
      • 此时我们发现,我们需要一个重要的新信息,即如果小力已经使用了「永久性改变」,我们需要知道他使用在哪个位置,这个信息在前文的讨论中是没有记录下来的。把它记录下来的办法有很多种,在这里我们可以把 \(f(i, x, y, s)\) 从一个数扩展成一个结构体,这个结构体里记录三个量 \((d, x_p, y_p)\),其中整数 \(d\) 就是我们之前定义的 \(f\) 的值,\((x_p, y_p)\) 表示小力在 \((x_p, y_p)\) 处使用了「永久性改变」。这个「扩展」也许不是一开始就想到的,是我们在慢慢形成思路的过程中想到的。如果我们决定使用「永久性改变」,这里的 \((x_p, y_p)\) 也要随之更新。
    • 如果 \(s = {\rm NONE\_USED }\),我们既可以选择使用一次「临时性改变」,也可以选择使用一次「永久性改变」
      • 如果选择「临时性改变」,则松弛 \((i, x, y, s)\)\((i + 1, x', y', {\rm ONLY\_TEMP})\)
      • 如果选择「永久性改变」,则松弛 \((i, x, y, s)\)\((i + 1, x', y', {\rm ONLY\_PERM})\)
    • 如果 \(s = {\rm TEMP\_PERM }\),则两次权利都已经使用,没有办法走到这个点

最后,如果在任意一个时刻 \(i\),任意一种 \(s\) 的情况下,终点的 \(f\) 的值不是 \(+\infty\),说明终点是可达的。

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using LL = long long;

const int dx[] = {0, 0, 1, -1, 0};
const int dy[] = {1, -1, 0, 0, 0};
const int
NONE_USED = 0,
ONLY_TEMP = 1,
ONLY_PERM = 2,
TEMP_PERM = 3;

struct StatusValue {
LL d;
int px, py;
StatusValue(LL d, int px, int py) {
this->d = d;
this->px = px;
this->py = py;
}

StatusValue() {}
} f[100 + 1][50 + 1][50 + 1][4];

struct Status {
int i, x, y, sc;
StatusValue v;

Status(int i, int x, int y, int sc, StatusValue v) {
this->i = i;
this->x = x;
this->y = y;
this->v = v;
this->sc = sc;
}
};

class Solution {
public:
vector<vector<string>> mazes;
int layers, r, c;

bool escapeMaze(vector<vector<string>>& mazes_) {
mazes = mazes_;
layers = mazes.size();
r = mazes[0].size();
c = mazes[0][0].size();

queue<Status> q;

for (int i = 0; i < layers; ++i) {
for (int x = 0; x < r; ++x) {
for (int y = 0; y < c; ++y) {
for (int sc = 0; sc < 4; ++sc) {
f[i][x][y][sc] = StatusValue(INT_MAX, -1, -1);
}
}
}
}

f[0][0][0][NONE_USED] = StatusValue(0, -1, -1);
q.push(Status(0, 0, 0, NONE_USED, f[0][0][0][NONE_USED]));

while (!q.empty()) {
auto frt = q.front();
q.pop();

int c_layer = frt.i, c_x = frt.x, c_y = frt.y, c_sc = frt.sc;
auto c_opt = frt.v;

int nex_layer = c_layer + 1;
if (!(nex_layer < layers)) {
continue;
}

for (int dir = 0; dir < 5; ++dir) {
int nx = c_x + dx[dir];
int ny = c_y + dy[dir];

if (!(nx >= 0 && nx < r && ny >= 0 && ny < c)) {
continue;
}

// can go
if (mazes[nex_layer][nx][ny] == '.') {
if (c_opt.d + 1 < f[nex_layer][nx][ny][c_sc].d) {
f[nex_layer][nx][ny][c_sc] = c_opt;
f[nex_layer][nx][ny][c_sc].d = c_opt.d + 1;
q.push(Status(nex_layer, nx, ny, c_sc, f[nex_layer][nx][ny][c_sc]));
}
continue;
}


// cannot go
// 1. ONLY_TEMP
if (c_sc == ONLY_TEMP) {
if (c_opt.d + 1 < f[nex_layer][nx][ny][TEMP_PERM].d) {
f[nex_layer][nx][ny][TEMP_PERM].d = c_opt.d + 1;
f[nex_layer][nx][ny][TEMP_PERM].px = nx;
f[nex_layer][nx][ny][TEMP_PERM].py = ny;
q.push(Status(nex_layer, nx, ny, TEMP_PERM, f[nex_layer][nx][ny][TEMP_PERM]));
}
}


// 2. ONLY_PERM
if (c_sc == ONLY_PERM) {
if (c_opt.px == nx && c_opt.py == ny) {
if (c_opt.d + 1 < f[nex_layer][nx][ny][c_sc].d) {
f[nex_layer][nx][ny][c_sc] = c_opt;
f[nex_layer][nx][ny][c_sc].d = c_opt.d + 1;
q.push(Status(nex_layer, nx, ny, c_sc, f[nex_layer][nx][ny][c_sc]));
}
} else {
if (c_opt.d + 1 < f[nex_layer][nx][ny][TEMP_PERM].d) {
f[nex_layer][nx][ny][TEMP_PERM] = c_opt;
f[nex_layer][nx][ny][TEMP_PERM].d = c_opt.d + 1;
q.push(Status(nex_layer, nx, ny, TEMP_PERM, f[nex_layer][nx][ny][TEMP_PERM]));
}
}
}

// 3. NONE_USED
if (c_sc == NONE_USED) {
if (c_opt.d + 1 < f[nex_layer][nx][ny][ONLY_PERM].d) {
f[nex_layer][nx][ny][ONLY_PERM].d = c_opt.d + 1;
f[nex_layer][nx][ny][ONLY_PERM].px = nx;
f[nex_layer][nx][ny][ONLY_PERM].py = ny;
q.push(Status(nex_layer, nx, ny, ONLY_PERM, f[nex_layer][nx][ny][ONLY_PERM]));
}

if (c_opt.d + 1 < f[nex_layer][nx][ny][ONLY_TEMP].d) {
f[nex_layer][nx][ny][ONLY_TEMP] = c_opt;
f[nex_layer][nx][ny][ONLY_TEMP].d = c_opt.d + 1;
q.push(Status(nex_layer, nx, ny, ONLY_TEMP, f[nex_layer][nx][ny][ONLY_TEMP]));
}
}
}

}

for (int i = 0; i < layers; ++i) {
for (int sc = 0; sc < 4; ++sc) {
if (f[i][r - 1][c - 1][sc].d != INT_MAX) {
return true;
}
}
}

return false;
}
};

复杂度

  • 时间复杂度:\(O(t \times n \times m \times 4) = O(t \times n \times m)\),其中 \(t\) 代表时刻总数。
  • 空间复杂度:\(O(t \times n \times m)\)

类似的题目