I have spent some time understand the logic that move the head->tail is valid. For example, a 3*3 grid, once you have 4 points (0,0), (0,1), (1,1), (1,0), where head is (0,0), and tail is (1, 0), if you move down (D), then the whole body get moved, and it is valid as (1,0), (0,0), (0, 1), (1, 1). This is the tricky part of this question.

```
public:
list<pair<int, int>> snake;
queue<pair<int, int>> foodque;
pair<int, int> currfood;
int m=0, n=0, totalFood = 0;
bool hasDied = false, isNotOccupied = true;
SnakeGame(int width, int height, vector<pair<int, int>> food) {
m = height; n = width;
for (pair<int, int>& fi : food) { foodque.push(fi); }
currfood = foodque.front();
foodque.pop();
totalFood = food.size();
snake.push_back({ 0, 0 });
isNotOccupied = !isOccupied(currfood);
}
/** 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) {
// time complexity is O(N), where N is the length of the snake
if (hasDied) { return -1; }
pair<int, int> front = snake.front();
pair<int, int> next = nextMove(front, direction);
if (!isValid(next)) {
hasDied = true;
return -1;
}
bool meetFood = false;
if (next.first == currfood.first
&& next.second == currfood.second
&& totalFood > 0
&& isNotOccupied) {
--totalFood;
meetFood = true;
if (foodque.size() > 0) {
currfood = foodque.front(); // get next one
foodque.pop();
}
}
snake.push_front(next);
if (!meetFood) {
snake.pop_back();
}
// after each move, update the currfood information to
// see if it can be updated
if (!isNotOccupied && totalFood>0) {
isNotOccupied = !isOccupied(currfood);
}
return snake.size() - 1;
}
bool isOccupied(pair<int, int>& currfood) {
// by occupied, it means it is not adjacent to the head or tail
for (pair<int, int>& p : snake) {
if (currfood.first == p.first && currfood.second == p.second) {
return true;
}
}
return false;
}
bool isValid(pair<int, int>& move) {
if (move.first < 0 || move.first >= m
|| move.second < 0 || move.second >= n) {
return false;
}
// NOTE that: if head==tail is okay
pair<int, int> tail = snake.back();
if(move.first==tail.first && move.second==tail.second) { return true; }
// check if the snake will move the head to its other body (not tail)
for (pair<int, int>& p : snake) {
if (p.first == move.first && p.second == move.second) {
return false;
}
}
return true;
}
pair<int, int> nextMove(pair<int, int>& curr, string dir) {
if (dir == "U") { return{ curr.first - 1, curr.second }; }
if (dir == "L") { return{ curr.first, curr.second - 1 }; }
if (dir == "R") { return{ curr.first, curr.second + 1 }; }
return{ curr.first + 1, curr.second };
}
```