# Java Solution O(n) for every move, since using Queue to check body position

• ``````public class SnakeGame {
private int width;
private int height;
private int currX;
private int currY;
private int[][] food;
private int fi;
// Need to track body movement
private Deque<String> snake;

// No need to use actual matrix.
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
}

// Snake cannot bite its own body! Need to keep track of body positions
// If food run out, return final score
public int move(String direction) {
if (direction.equals("U")) currY -= 1;
if (direction.equals("D")) currY += 1;
if (direction.equals("L")) currX -= 1;
if (direction.equals("R")) currX += 1;

String coors = currY + "," + currX;

if (currX < 0 || currY < 0 || currX >= width || currY >= height || snake.contains(coors)) return -1;

// move one forward
String last = snake.removeLast();

// done all foods
if (fi >= food.length) return snake.size();

// eat food
if (food[fi][0] == currY && food[fi][1] == currX) {
snake.add(last);    // add removed piece due to movement; the extra "food" eaten
fi++;
}
return snake.size();
}
``````

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