难度: Medium
Submission
运行时间: 164 ms
内存: 18.7 MB
class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.score = 0
self.snake_dict = {(0, 0): 1}
self.width = width
self.height = height
self.food = food
self.food_index = 0
self.snake = deque([(0, 0)])
self.movement = {"R": [0, 1], "D": [1, 0], "U": [-1, 0], "L": [0, -1]}
def move(self, direction: str) -> int:
head = self.snake[0]
newhead = (
head[0] + self.movement[direction][0],
head[1] + self.movement[direction][1],
)
# 判断是否出界
if not (
newhead[0] < self.height
and newhead[0] >= 0
and newhead[1] < self.width
and newhead[1] >= 0
):
return -1
# 判断是否吃到自己
if newhead in self.snake_dict and newhead != self.snake[-1]:
return -1
self.snake.appendleft(newhead)
# 是否能吃到
if self.food_index < len(self.food) and newhead == tuple(
self.food[self.food_index]
):
self.score += 1
self.food_index += 1
else:
tail = self.snake.pop()
del self.snake_dict[tail]
self.snake_dict[newhead] = 1
return self.score
# Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)
Explain
该题解使用双端队列 deque 和字典来模拟贪吃蛇游戏。字典 snake_dict 存储蛇身体每一节的位置，双端队列 snake 存储蛇身体的位置。move 方法根据给定的方向移动蛇头，同时判断是否出界、是否吃到自己以及是否吃到食物。如果吃到食物，则分数加 1，食物索引加 1；否则，将蛇尾从双端队列和字典中删除。最后，将新的蛇头位置加入双端队列和字典中。
时间复杂度: O(1)
空间复杂度: O(width * height)
class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.score = 0
self.snake_dict = {(0, 0): 1} # 存储蛇身体每一节的位置
self.width = width
self.height = height
self.food = food
self.food_index = 0
self.snake = deque([(0, 0)]) # 双端队列存储蛇身体的位置
self.movement = {"R": [0, 1], "D": [1, 0], "U": [-1, 0], "L": [0, -1]} # 移动方向
def move(self, direction: str) -> int:
head = self.snake[0]
newhead = (
head[0] + self.movement[direction][0],
head[1] + self.movement[direction][1],
) # 计算新蛇头的位置
# 判断是否出界
if not (
newhead[0] < self.height
and newhead[0] >= 0
and newhead[1] < self.width
and newhead[1] >= 0
):
return -1
# 判断是否吃到自己
if newhead in self.snake_dict and newhead != self.snake[-1]:
return -1
self.snake.appendleft(newhead) # 将新蛇头加入双端队列
# 判断是否吃到食物
if self.food_index < len(self.food) and newhead == tuple(
self.food[self.food_index]
):
self.score += 1 # 更新分数
self.food_index += 1 # 更新食物索引
else:
tail = self.snake.pop() # 移除蛇尾
del self.snake_dict[tail] # 从字典中删除蛇尾
self.snake_dict[newhead] = 1 # 将新蛇头加入字典
return self.score
Explore
在贪吃蛇游戏中，每个位置只能被蛇身的一部分占据。如果新的蛇头位置已存在于蛇身字典中，这通常意味着蛇头即将进入其身体的其它部分，从而导致游戏结束。检查新位置是否在字典中是为了确认蛇头是否撞到了自己的身体。此外，有一个特殊情况需考虑：当蛇头移动到蛇尾的位置（即将蛇尾移动到新的头部位置）而此时不引入食物时，这不应被认为是蛇吃到自己。因此，除非新蛇头的位置与蛇尾的位置相同（这种情况下蛇尾即将被移除），否则，新蛇头位置在字典中的存在确实表明蛇吃到了自己。
在贪吃蛇游戏中，每当蛇吃到食物时，蛇的长度会增加。因此，当蛇吃到食物后，蛇尾部分不会移动，蛇头部则增加新的部分，这样整体长度增加一格，所以不需要从字典中删除蛇尾的记录。相反，如果没有吃到食物，蛇需要在保持长度不变的情况下前进，这时蛇尾的最后一格将被移除，因此需要从字典中删除蛇尾的记录，以反映蛇体的这一变化。
使用双端队列(deque)来存储蛇的位置可以高效地在两端添加或删除元素。在贪吃蛇游戏中，这意味着可以快速地在蛇头添加新的部分（当蛇移动或吃到食物时），同时也可以快速地移除蛇尾部分（当蛇向前移动而没有吃到食物时）。字典用于快速检查任何给定位置是否已被蛇身占据，这是检查蛇是否撞到自己的关键。因此，这两种数据结构的组合提供了既高效又方便的方式来管理蛇的状态变化。
蛇头新位置的计算是基于当前蛇头的位置加上一个由移动方向决定的向量。在实现中，定义了一个移动方向到向量的映射（movement字典），其中包括了'U'（上移，坐标变化为[-1, 0]），'D'（下移，坐标变化为[1, 0]），'L'（左移，坐标变化为[0, -1]），以及'R'（右移，坐标变化为[0, 1]）。通过获取蛇头当前的位置并将其与对应方向的向量相加，可得到新的蛇头位置。例如，如果蛇头当前位置是(2, 3)并指定向右移动，则新的蛇头位置将是(2, 3+1)=(2, 4)。这种方式确保了新位置的计算既直观又符合逻辑的坐标系统，容易进行验证和调整。