# C++, List, Easy code. Note: move head to tail is valid operation!

• 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 };
}``````

• It's naive but works OK. when given a direction, we can get the position of next move, and see if the move is out of boundary,or there's food there, or it's just a normal move.

``````public class SnakeGame{
int[][] food;
int width;
int height;
int index;
Deque<String> q;
public static final HashMap<String,int[]> map=new HashMap<String,int[]>(){
{
put("U",new int[]{-1,0});
put("D",new int[]{1,0});
put("L",new int[]{0,-1});
put("R",new int[]{0,1});
}
};
public SnakeGame(int width,int height,int[][] food){
this.food=food;
this.width=width;
this.height=height;
int index;
q.offer(new String("0 0"));
}

public int move(String direction){
String[] curr=q.peekLast().split(" ");
int[] dir=map.get(direction);
//based on the direction given, we derive next move
int x=Integer.parseInt(curr[0])+dir[0];
int y=Integer.parseInt(curr[1])+dir[1];

//if next move will go beyond the boundary, or cross snake's body
if(x<0||x>height-1||y<0||y>width-1||q.contains(x+" "+y)&&!q.peek().equals(x+" "+y)){
return -1;
}
//if there's food on the next move, then this position will become part of the snake body
if(index<food.length){
int xFood=food[index][0];
int yFood=food[index][1];
if(x==xFood&&y==yFood){
q.offer(x+" "+y);
index++;
return index;
}
}

//normal move:neither we go cross boundary,nor we get food on the next move;we just move the   snake one step forward
q.offer(x+" "+y);
q.poll();
return index;
}
``````

}

• Hey I like your answer and upvote it for sure! I wrote another one and try to post it..I've never posted and it seems that I am posting at wrong place, hope you don't mind:)

• thanks, it is also my first time to get an up vote ^_^

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.