# 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] && col == food[pos]) {
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);
*/
``````