leetcode
leetcode 3001 ~ 3050
弹珠游戏

弹珠游戏

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 64 ms, 内存: 23.0 MB


解释

方法:

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

时间复杂度:

O((m+n) * num)

空间复杂度:

O(m+n)

代码细节讲解

🦆
解题思路中提到的DIRS数组是如何决定方向的,为什么这样的顺序可以覆盖所有需要的方向?
DIRS数组用于表示弹珠在二维平面上的移动方向,其中每个元组的两个元素分别对应x轴和y轴的移动步长。数组中的四个元组分别表示向右、向下、向左、向上的方向,这对应于顺时针旋转。这样的顺序是因为在题解中,需要处理弹珠遇到转向器时的方向变化。顺时针转向器('E')使得弹珠方向序号增加1,而逆时针转向器('W')则使方向序号增加3(等价于顺时针方向减1)。通过模运算保证方向序号在0到3之间循环,从而覆盖所有可能的方向变化。
🦆
对于check函数中的边界检查`if not (0 <= x < m and 0 <= y < n): return False`,这个条件是如何确保弹珠不会越界的?
这个边界检查条件确保了弹珠的坐标(x, y)始终在有效的游戏板范围内。条件`0 <= x < m`和`0 <= y < n`分别检查弹珠的x坐标和y坐标是否在游戏板的行和列的有效索引范围内。如果弹珠的任意坐标超出这个范围,即意味着弹珠已经移动到了游戏板的外面,因此函数返回False表示弹珠不能继续在板上合法移动。
🦆
在模拟弹珠运动时,遇到'W'和'E'时如何决定弹珠的新方向?具体的逻辑是怎样的?
在模拟过程中,当弹珠遇到字符'W',意味着需要将弹珠的移动方向顺时针转动270度(等同于逆时针转动90度),在DIRS数组中实现这一转向是通过将当前方向d的值增加3再对4取模来完成。同理,当弹珠遇到字符'E',表示需要将弹珠的移动方向顺时针转动90度,这是通过将当前方向d的值增加1再对4取模来实现。这些操作保证了弹珠的方向始终处于DIRS数组定义的四个方向中的一个,并能正确地响应转向器的效果。

相关问题