弹珠游戏

难度: Medium

欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。 `N*M` 大小的弹珠盘的初始状态信息记录于一维字符串型数组 `plate` 中，数组中的每个元素为仅由 `"O"`、`"W"`、`"E"`、`"."` 组成的字符串。其中： - `"O"` 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）； - `"W"` 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）； - `"E"` 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）； - `"."` 表示空白区域（弹珠可通行）。游戏规则要求仅能在边缘位置的 **空白区域** 处（弹珠盘的四角除外）沿 **与边缘垂直** 的方向打入弹珠，并且打入后的每颗弹珠最多能 **前进** `num` 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 **按任意顺序** 返回答案。 **注意：** - 若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。 **示例 1：** > 输入： >`num = 4` >`plate = ["..E.",".EOW","..W."]` > > 输出：`[[2,1]]` > > 解释： > 在 `[2,1]` 处打入弹珠，弹珠前进 1 步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。 ![b054955158a99167b8d51da0e22a54da.gif](https://pic.leetcode-cn.com/1630392649-BoQncz-b054955158a99167b8d51da0e22a54da.gif){:width="300px"} **示例 2：** > 输入： >`num = 5` >`plate = [".....","..E..",".WO..","....."]` > > 输出：`[[0,1],[1,0],[2,4],[3,2]]` > > 解释： > 在 `[0,1]` 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向逆时针旋转 90 度，再前进 1 步进入洞中。 > 在 `[1,0]` 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向顺时针旋转 90 度，再前进 1 步进入洞中。 > 在 `[2,4]` 处打入弹珠，弹珠前进 2 步后进入洞中。 > 在 `[3,2]` 处打入弹珠，弹珠前进 1 步后进入洞中。 ![b44e9963239ae368badf3d00b7563087.gif](https://pic.leetcode-cn.com/1630392625-rckbdy-b44e9963239ae368badf3d00b7563087.gif){:width="350px"} **示例 3：** > 输入： >`num = 3` >`plate = [".....","....O","....O","....."]` > > 输出：`[]` > > 解释： > 由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。 **提示：** - `1 <= num <= 10^6` - `1 <= plate.length, plate[i].length <= 1000` - `plate[i][j]` 仅包含 `"O"`、`"W"`、`"E"`、`"."`

Submission

运行时间: 64 ms

内存: 23.0 MB

DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）
class Solution:
    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:
        m, n = len(plate), len(plate[0])
        def check(x: int, y: int, d: int) -> bool:
            left = num
            while plate[x][y] != 'O':
                if left == 0: return False  # 无剩余步数
                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针
                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针
                x += DIRS[d][0]
                y += DIRS[d][1]
                if not (0 <= x < m and 0 <= y < n): return False  # 出界
                left -= 1
            return True

        ans = []
        for j in range(1, n - 1):
            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边
            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边
        for i in range(1, m - 1):
            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边
            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边
        return ans

Explain

解题思路是通过模拟弹珠的运动路径来确定哪些初始位置可以让弹珠最终落入洞中。首先定义了四个基本方向对应的坐标变化。对于盘边的每个空白位置，根据其在边上的位置确定其初始方向，并使用check函数模拟弹珠的运动。在这个函数中，弹珠会根据当前位置的字符改变方向或直接前进，直至弹珠落入洞中、走出边界或步数耗尽。最后，将所有可以使弹珠入洞的初始位置记录并返回。

时间复杂度: O((m+n) * num)

空间复杂度: O(m+n)

DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）
class Solution:
    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:
        m, n = len(plate), len(plate[0])
        def check(x: int, y: int, d: int) -> bool:
            left = num
            while plate[x][y] != 'O':
                if left == 0: return False  # 若步数用尽，返回失败
                if plate[x][y] == 'W':   d = (d + 3) % 4  # 遇逆时针转向器，转向
                elif plate[x][y] == 'E': d = (d + 1) % 4  # 遇顺时针转向器，转向
                x += DIRS[d][0]
                y += DIRS[d][1]
                if not (0 <= x < m and 0 <= y < n): return False  # 检测是否出界
                left -= 1
            return True

        ans = []
        for j in range(1, n - 1):
            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 检查上边界
            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 检查下边界
        for i in range(1, m - 1):
            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 检查左边界
            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 检查右边界
        return ans

Explore

DIRS数组用于表示弹珠在二维平面上的移动方向，其中每个元组的两个元素分别对应x轴和y轴的移动步长。数组中的四个元组分别表示向右、向下、向左、向上的方向，这对应于顺时针旋转。这样的顺序是因为在题解中，需要处理弹珠遇到转向器时的方向变化。顺时针转向器（'E'）使得弹珠方向序号增加1，而逆时针转向器（'W'）则使方向序号增加3（等价于顺时针方向减1）。通过模运算保证方向序号在0到3之间循环，从而覆盖所有可能的方向变化。

这个边界检查条件确保了弹珠的坐标(x, y)始终在有效的游戏板范围内。条件`0 <= x < m`和`0 <= y < n`分别检查弹珠的x坐标和y坐标是否在游戏板的行和列的有效索引范围内。如果弹珠的任意坐标超出这个范围，即意味着弹珠已经移动到了游戏板的外面，因此函数返回False表示弹珠不能继续在板上合法移动。

在模拟过程中，当弹珠遇到字符'W'，意味着需要将弹珠的移动方向顺时针转动270度（等同于逆时针转动90度），在DIRS数组中实现这一转向是通过将当前方向d的值增加3再对4取模来完成。同理，当弹珠遇到字符'E'，表示需要将弹珠的移动方向顺时针转动90度，这是通过将当前方向d的值增加1再对4取模来实现。这些操作保证了弹珠的方向始终处于DIRS数组定义的四个方向中的一个，并能正确地响应转向器的效果。