# 353 - Design Snake Game

解法一 - Deque + Hashset

把蛇分成兩種狀態：

1. 走路 - 因為走路時頭會增加新的點，尾巴會減少一個點，所以用 deque，這樣修改頭尾都很方便

2. 吃東西 - 不能碰到自己，所以把身體存到 Hash Set 中，檢查不會碰到身體

class SnakeGame {
public:
    /** Initialize your data structure here.
        @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]. */
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->food = food;
        w = width, h = height, pos = 0;
        q.push_back(make_pair(0, 0));
    }

    /** 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. */
    int move(string direction) {
        // Erase tail and move head
        int row = q.back().first, col = q.back().second;
        pair<int, int> d = q.front();
        q.pop_front();
        hist.erase(d);

        if (direction == "U")
            row--;
        else if (direction == "D")
            row++;
        else if (direction == "L")
            col--;
        else if (direction == "R")
            col++;

        // Corner case: 1. move to boundary, 2. eat itself
        if (row < 0 || col < 0 || col >= w || row >= h || hist.count(make_pair(row, col))) {
            return -1;
        }

        // Case 1: Walk
        hist.insert(make_pair(row, col));
        q.push_back(make_pair(row, col));

        // Case 2: Eat
        if (pos >= food.size()) {
            return q.size() - 1;
        }

        if (row == food[pos][0] && col == food[pos][1]) {
            pos++;
            q.push_front(d);
            hist.insert(d);
        }

        return q.size() - 1;        
    }

private:
    int w, h, pos; // pos indicate which food we are eating
    vector<vector<int>> food;
    set< pair<int, int> > hist;
    deque<pair<int, int>> q;
};

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