2022力扣秋季赛第3题

  |  

摘要: 2022 力扣秋季赛第 3 题,比较复杂的多源 BFS 题目

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们来研究一下力扣秋季赛第 3 题,也就是 LCP63,本题是在多源 BFS 的基础上增加了些状态定义和状态转移的复杂性,总体上还是挺复杂的。

在比赛的时候也确实一下就想到了多源 BFS,但是状态有些复杂,实现上出了不少问题,错了一次,超时一次,最后磕磕绊绊过了。

在上一篇文章 力扣1162-多源BFS与多源最短路径 中,我们以力扣 1162 为例看了最简单的多源 BFS 的算法和实现。那个题的状态就是一个位置坐标 (x, y),状态转移的规则就是按照上下左右四个方向走,不走重复的点就可以。本题的状态定义和状态转移规则可以对比一下,会稍微复杂一点。

题目

LCP 63. 弹珠游戏

N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中,数组中的每个元素为仅由 “O”、”W”、”E”、”.” 组成的字符串。其中:

  • “O” 表示弹珠洞(弹珠到达后会落入洞中,并停止前进);
  • “W” 表示逆时针转向器(弹珠经过时方向将逆时针旋转 90 度);
  • “E” 表示顺时针转向器(弹珠经过时方向将顺时针旋转 90 度);
  • “.” 表示空白区域(弹珠可通行)。

游戏规则要求仅能在边缘位置的 空白区域 处(弹珠盘的四角除外)沿 与边缘垂直 的方向打入弹珠,并且打入后的每颗弹珠最多能 前进 num 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。

注意:

若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进,则将直接出界。

提示:

1
2
3
1 <= num <= 10^6
1 <= plate.length, plate[i].length <= 1000
plate[i][j] 仅包含 "O"、"W"、"E"、"."

示例:

输入:
num = 4
plate = [“..E.”,”.EOW”,”..W.”]
输出:[[2,1]]
解释:
在 [2,1] 处打入弹珠,弹珠前进 1 步后遇到转向器,前进方向顺时针旋转 90 度,再前进 1 步进入洞中。

算法: 多源BFS

本题要求的是给定的点集中,有哪些是可以在规定步数内到达给定点的,场景与力扣 1162 基本一样,多源 BFS 的整体的思路就是将所有源点压入队列,然后一层一层地按 BFS 进行前进,如果某个点在前进过程中到达了目标点就把结果记录一下,如果超过步数则该点停止前进。

一个点在 BFS 过程中的状态定义如下:

1
2
3
4
5
6
7
struct State
{
int x, y, d;
int ori_x, ori_y;
State(){}
State(int x, int y, int d, int ori_x, int ori_y):x(x),y(y),d(d),ori_x(ori_x),ori_y(ori_y){}
};

其中 x, y 表示当前的位置坐标,这与力扣 1162 是一样的。

在力扣 1162 中,我们只需要访问到距离最近的点即可,并不需要知道最近的距离是多少。而本题需要满足总步数小于给定值的要求,这就需要在走的时候记录步数,因此状态中需要加上表示步数的字段 d。

当走到给定位置的时候,在力扣 1162 中我们要求的就是走到的位置本身,因此不需要额外记录信息,而本题要求的是对应的起点,这就需要记录一个不随步数变化的属性信息,也就是起点位置 x_ori, y_ori。

下面看一下一个点在 BFS 过程中的状态转移规则,在力扣 1162 中,只需要遍历 4 个方向,只要判断一下下一个点是否之前访问过即可。而本题的方向是规定好的,且在特定的位置需要改变方向,因此判断当前点是否需要改方向。

我们把四个方向的 dx, dy 按照顺时针改变的顺序组织好:

1
2
3
// 右,下,左, 上
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

如果当前的方向是 (dx[d], dy[d]),则顺时针只需要 d = (d + 1) % 4 即可,逆时针只需要 d = (d - 1) % 4 即可。

代码 (C++)

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
struct State
{
int x, y, d;
int ori_x, ori_y;
State(){}
State(int x, int y, int d, int ori_x, int ori_y):x(x),y(y),d(d),ori_x(ori_x),ori_y(ori_y){}
};

class Solution {
public:
vector<vector<int>> ballGame(int num, vector<string>& plate) {
int n = plate.size();
int m = plate[0].size();

// 右,下,左, 上
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

queue<State> q;
// 压入源点
// (i, 0, 0)
for(int i = 1; i < n - 1; ++i)
if(plate[i][0] == '.')
q.push(State(i, 0, 0, i, 0));
// (i, m - 1, 2)
for(int i = 1; i < n - 1; ++i)
if(plate[i][m - 1] == '.')
q.push(State(i, m - 1, 2, i, m - 1));
// (0, j, 1)
for(int j = 1; j < m - 1; ++j)
if(plate[0][j] == '.')
q.push(State(0, j, 1, 0, j));
// (n - 1, j, 3)
for(int j = 1; j < m - 1; ++j)
if(plate[n - 1][j] == '.')
q.push(State(n - 1, j, 3, n - 1, j));

vector<vector<int>> result;
vector<State> level_nodes;

while(!q.empty() && num > 0)
{
level_nodes.clear();
while(!q.empty())
{
State cur = q.front();
q.pop();
int x = cur.x + dx[cur.d];
int y = cur.y + dy[cur.d];
int d = cur.d;
if(x >= n || x < 0 || y >= m || y < 0)
continue;
if(plate[x][y] == 'O')
{
result.push_back({cur.ori_x, cur.ori_y});
continue;
}
else if(plate[x][y] == 'E')
d = (d + 1) % 4;
else if(plate[x][y] == 'W')
d = (d + 3) % 4;

State s = cur;
s.x = x;
s.y = y;
s.d = d;

level_nodes.push_back(s);
}
for(State s: level_nodes)
q.push(s);
--num;
}
return result;
}
};

Share