题目描述

Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game’s score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

样例

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

思路

蛇有上下左右4个移动方向，注意每次移动都是同时移动，所以长度为4的时候不会咬到自己的尾巴（需要断尾操作）。而且食物不会出现在蛇的位置上。
如何检测新的蛇头是不是撞在身体上：
1. 遍历 deque
2. 用set，但是c++ 的set不支持 pair<int,int> 类型，所以我们需要把 pair<int,int> 类型抽象成 position class 并且重载’=’号。但是这里food 数量小于 50，所以直接遍历的时间复杂度可以估计为 $O(1)$

C++ 代码

class SnakeGame {
private:
    deque<pair<int,int>> snake;
    vector<vector<int>> food;
    int width;
    int height;
    int foodCnt;

public:
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->width = width;
        this->height = height;
        this->food = food;
        this->foodCnt = 0;
        this->snake.push_back({0, 0});
    }

    int move(string direction) {
        // deque 里我们的队尾是蛇头，每走一步我们都把新的蛇头位置添加到队尾
        auto oldHead = snake.back();
        // 初始化蛇头坐标
        int dx = oldHead.first;
        int dy = oldHead.second;
        // 断尾操作
        auto tail = snake.front();
        snake.pop_front();
        // 更新我们蛇头的新坐标, 坐标系是x轴往下，y轴往右
        if (direction == "U") dx--;
        else if (direction == "D") dx++;
        else if (direction == "L") dy--;
        else dy++;

        // 如果出界或者咬到自己就 game over，注意提前断尾巴
        if (dx < 0 || dx >= height || dy < 0 || dy >= width) return -1;

        // 咬到自己只能用O(n)的时间，因为c++里 set 不支持 pair<int,int> 类型
        // 如果要用 set，我们需要把所有的 pair<int,int> 改成 结构体 position 并且 重载'='号
        for (auto &[r, c] : snake) { // 检测蛇头是否与身体相撞
            if (dx == r && dy == c) return -1;
        }

        // 加上新蛇头的坐标
        snake.push_back({dx, dy});

        // 如果食物没有吃完，并且新头部咬到了食物，尾巴接回来
        // 注意食物不会在蛇的位置生成
        if (foodCnt != food.size() && food[foodCnt][0] == dx && food[foodCnt][1] == dy) {
            snake.push_front(tail);
            foodCnt++;
        }
        return foodCnt;
    }
};

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