Question

353. 贪吃蛇

English Version

题目描述

请你设计一个 贪吃蛇游戏，该游戏将会在一个 屏幕尺寸 = 宽度 x 高度 的屏幕上运行。如果你不熟悉这个游戏，可以 点击这里 在线试玩。

起初时，蛇在左上角的 (0, 0) 位置，身体长度为 1 个单位。

你将会被给出一个数组形式的食物位置序列 food ，其中 food[i] = (ri, ci) 。当蛇吃到食物时，身子的长度会增加 1 个单位，得分也会 +1 。

食物不会同时出现，会按列表的顺序逐一显示在屏幕上。比方讲，第一个食物被蛇吃掉后，第二个食物才会出现。

当一个食物在屏幕上出现时，保证 不会 出现在被蛇身体占据的格子里。

如果蛇越界（与边界相撞）或者头与 移动后 的身体相撞（即，身长为 4 的蛇无法与自己相撞），游戏结束。

实现 SnakeGame 类：

• SnakeGame(int width, int height, int[][] food) 初始化对象，屏幕大小为 height x width ，食物位置序列为 food
• int move(String direction) 返回蛇在方向 direction 上移动后的得分。如果游戏结束，返回 -1 。

 

示例 1：

输入：
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
输出：
[null, 0, 0, 1, 1, 2, -1]

解释：
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // 返回 0
snakeGame.move("D"); // 返回 0
snakeGame.move("R"); // 返回 1 ，蛇吃掉了第一个食物，同时第二个食物出现在 (0, 1)
snakeGame.move("U"); // 返回 1
snakeGame.move("L"); // 返回 2 ，蛇吃掉了第二个食物，没有出现更多食物
snakeGame.move("U"); // 返回 -1 ，蛇与边界相撞，游戏结束

 

提示：

• 1 <= width, height <= 104
• 1 <= food.length <= 50
• food[i].length == 2
• 0 <= ri < height
• 0 <= ci < width
• direction.length == 1
• direction is 'U', 'D', 'L', or 'R'.
• 最多调用 104 次 move 方法

解法

方法一：双端队列模拟

我们可以使用双端队列来模拟蛇的移动。

定义一个双端队列 $q$，其中保存蛇的身体坐标，队头为蛇头，队尾为蛇尾。同时使用一个集合 $vis$ 来保存蛇的身体坐标，用于快速判断蛇头是否与蛇身相撞。

定义一个变量 $score$ 来保存蛇的得分，初始值为 $0$；定义一个变量 $idx$ 来保存当前食物的索引，初始值为 $0$。

每次移动时，首先判断蛇头是否与边界相撞，如果相撞则游戏结束，返回 $-1$；否则，判断蛇头是否与食物重合，如果重合则蛇的得分加 $1$，同时食物索引 $idx$ 加 $1$；否则，蛇的身体长度不变，需要将蛇尾从队尾弹出，并从集合 $vis$ 中删除对应的坐标。

然后，判断蛇头是否与蛇身相撞，如果相撞则游戏结束，返回 $-1$；否则，将蛇头的坐标加入集合 $vis$ 中，并从队头加入蛇头的坐标。

最后，返回蛇的得分 $score$。

时间复杂度 $O(k)$，空间复杂度 $O(k)$，其中 $k$ 为移动的次数。

class SnakeGame:
  def __init__(self, width: int, height: int, food: List[List[int]]):
    self.m = height
    self.n = width
    self.food = food
    self.score = 0
    self.idx = 0
    self.q = deque([(0, 0)])
    self.vis = {(0, 0)}

  def move(self, direction: str) -> int:
    i, j = self.q[0]
    x, y = i, j
    match direction:
      case "U":
        x -= 1
      case "D":
        x += 1
      case "L":
        y -= 1
      case "R":
        y += 1
    if x < 0 or x >= self.m or y < 0 or y >= self.n:
      return -1
    if (
      self.idx < len(self.food)
      and x == self.food[self.idx][0]
      and y == self.food[self.idx][1]
    ):
      self.score += 1
      self.idx += 1
    else:
      self.vis.remove(self.q.pop())
    if (x, y) in self.vis:
      return -1
    self.q.appendleft((x, y))
    self.vis.add((x, y))
    return self.score


# Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)

class SnakeGame {
  private int m;
  private int n;
  private int[][] food;
  private int score;
  private int idx;
  private Deque<Integer> q = new ArrayDeque<>();
  private Set<Integer> vis = new HashSet<>();

  public SnakeGame(int width, int height, int[][] food) {
    m = height;
    n = width;
    this.food = food;
    q.offer(0);
    vis.add(0);
  }

  public int move(String direction) {
    int p = q.peekFirst();
    int i = p / n, j = p % n;
    int x = i, y = j;
    if ("U".equals(direction)) {
      --x;
    } else if ("D".equals(direction)) {
      ++x;
    } else if ("L".equals(direction)) {
      --y;
    } else {
      ++y;
    }
    if (x < 0 || x >= m || y < 0 || y >= n) {
      return -1;
    }
    if (idx < food.length && x == food[idx][0] && y == food[idx][1]) {
      ++score;
      ++idx;
    } else {
      int t = q.pollLast();
      vis.remove(t);
    }
    int cur = f(x, y);
    if (vis.contains(cur)) {
      return -1;
    }
    q.offerFirst(cur);
    vis.add(cur);
    return score;
  }

  private int f(int i, int j) {
    return i * n + j;
  }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

class SnakeGame {
public:
  SnakeGame(int width, int height, vector<vector<int>>& food) {
    m = height;
    n = width;
    this->food = food;
    score = 0;
    idx = 0;
    q.push_back(0);
    vis.insert(0);
  }

  int move(string direction) {
    int p = q.front();
    int i = p / n, j = p % n;
    int x = i, y = j;
    if (direction == "U") {
      --x;
    } else if (direction == "D") {
      ++x;
    } else if (direction == "L") {
      --y;
    } else {
      ++y;
    }
    if (x < 0 || x >= m || y < 0 || y >= n) {
      return -1;
    }
    if (idx < food.size() && x == food[idx][0] && y == food[idx][1]) {
      ++score;
      ++idx;
    } else {
      int tail = q.back();
      q.pop_back();
      vis.erase(tail);
    }
    int cur = f(x, y);
    if (vis.count(cur)) {
      return -1;
    }
    q.push_front(cur);
    vis.insert(cur);
    return score;
  }

private:
  int m;
  int n;
  vector<vector<int>> food;
  int score;
  int idx;
  deque<int> q;
  unordered_set<int> vis;

  int f(int i, int j) {
    return i * n + j;
  }
};

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame* obj = new SnakeGame(width, height, food);
 * int param_1 = obj->move(direction);
 */

type SnakeGame struct {
  m   int
  n   int
  food  [][]int
  score int
  idx   int
  q   []int
  vis   map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
  return SnakeGame{height, width, food, 0, 0, []int{0}, map[int]bool{}}
}

func (this *SnakeGame) Move(direction string) int {
  f := func(i, j int) int {
    return i*this.n + j
  }
  p := this.q[0]
  i, j := p/this.n, p%this.n
  x, y := i, j
  if direction == "U" {
    x--
  } else if direction == "D" {
    x++
  } else if direction == "L" {
    y--
  } else {
    y++
  }
  if x < 0 || x >= this.m || y < 0 || y >= this.n {
    return -1
  }
  if this.idx < len(this.food) && x == this.food[this.idx][0] && y == this.food[this.idx][1] {
    this.score++
    this.idx++
  } else {
    t := this.q[len(this.q)-1]
    this.q = this.q[:len(this.q)-1]
    this.vis[t] = false
  }
  cur := f(x, y)
  if this.vis[cur] {
    return -1
  }
  this.q = append([]int{cur}, this.q...)
  this.vis[cur] = true
  return this.score
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * obj := Constructor(width, height, food);
 * param_1 := obj.Move(direction);
 */

class SnakeGame {
  private m: number;
  private n: number;
  private food: number[][];
  private score: number;
  private idx: number;
  private q: number[];
  private vis: Set<number>;

  constructor(width: number, height: number, food: number[][]) {
    this.m = height;
    this.n = width;
    this.food = food;
    this.score = 0;
    this.idx = 0;
    this.q = [0];
    this.vis = new Set([0]);
  }

  move(direction: string): number {
    const p = this.q[0];
    const i = Math.floor(p / this.n);
    const j = p % this.n;
    let x = i;
    let y = j;
    if (direction === 'U') {
      --x;
    } else if (direction === 'D') {
      ++x;
    } else if (direction === 'L') {
      --y;
    } else {
      ++y;
    }
    if (x < 0 || x >= this.m || y < 0 || y >= this.n) {
      return -1;
    }
    if (
      this.idx < this.food.length &&
      x === this.food[this.idx][0] &&
      y === this.food[this.idx][1]
    ) {
      ++this.score;
      ++this.idx;
    } else {
      const t = this.q.pop()!;
      this.vis.delete(t);
    }
    const cur = x * this.n + y;
    if (this.vis.has(cur)) {
      return -1;
    }
    this.q.unshift(cur);
    this.vis.add(cur);
    return this.score;
  }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * var obj = new SnakeGame(width, height, food)
 * var param_1 = obj.move(direction)
 */