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 <= 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 过程中的状态定义如下：

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 按照顺时针改变的顺序组织好：

// 右，下，左， 上
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++)

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;
    }
};

---