# LeetCode: 353. 贪吃蛇¶

## 1、题目描述¶

给定 width = 3, height = 2, 食物序列为 food = [[1,2],[0,1]]。

Snake snake = new Snake(width, height, food);

|S| | |
| | |F|

snake.move("R"); -> 函数返回 0

| |S| |
| | |F|

snake.move("D"); -> 函数返回 0

| | | |
| |S|F|

snake.move("R"); -> 函数返回 1 (蛇吃掉了第一个食物，同时第二个食物出现在位置 (0,1))

| |F| |
| |S|S|

snake.move("U"); -> 函数返回 1

| |F|S|
| | |S|

snake.move("L"); -> 函数返回 2 (蛇吃掉了第二个食物)

| |S|S|
| | |S|

snake.move("U"); -> 函数返回 -1 (蛇与边界相撞，游戏结束)


## 2、解题思路¶

• 使用队列保存蛇的身体
• 每次判断前进的步伐是否还在屏幕上面
• 如果还有食物，判断能否吃到食物
• 如果没有食物或不能吃到食物，蛇需要前进，将尾部节点移除，然后判断下一个节点能否撞到身体，撞到则返回-1
• 将下一个节点加入蛇的身体

from collections import deque

class SnakeGame:

def __init__(self, width: int, height: int, food: List[List[int]]):
"""
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
"""
self.row = height
self.col = width
self.food = food
self.food_pos = 0
self.snake = deque([(0, 0)])
self.snake_set = {(0, 0), }

def move(self, direction: str) -> int:
"""
Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body.
"""

# 坐标验证
def available(m, n):
return 0 <= m < self.row and 0 <= n < self.col

next_pos = [-1, -1]

if direction == "U":
elif direction == "D":
elif direction == "L":
elif direction == "R":

if not available(*next_pos):
return -1

# eat food ?
if self.food_pos < len(self.food) and next_pos == self.food[self.food_pos]:
self.food_pos += 1
else:
self.snake_set.remove(self.snake.popleft())

if tuple(next_pos) in self.snake_set:
return -1

self.snake.append((next_pos[0], next_pos[1]))