Accepted Java Solution

• First, I think the problem needs a few clarification:

1. The game should somehow guarantee that next food, which is predefined in the array, shall never appear on a cell which happens to be occupied by the snake.
2. It's OK to "turn back", such as: Head,Tail -> Tail, Head, which means tail moves first, then head.
3. If all the foods are exhausted, the game will continue, without any food appearing.

So trick is: use a LinkedList to track the snake; each move, we remove the tail (last element) and add a new head; if the snake eats a food, then tail stays but head extends. Use a set to track the body so if the new head exists in the set, return -1.

``````private int width, height;
int[][] food;
private int score, idx;
private Deque<Integer> snake;
private Set<Integer> body;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
score = 0;
idx = 0;
body = new HashSet<>();
}

public int move(String direction) {
// first of all, get head
int h = snake.getFirst() / width, w = snake.getFirst() % width;
if (direction.equals("U")) h--;
else if (direction.equals("D")) h++;
else if (direction.equals("L")) w--;
else w++;
if (w < 0 || w == width || h < 0 || h == height) return -1;
int head = h*width + w;
if (idx < food.length && h == food[idx][0] && w == food[idx][1]) {
score++; // and still keep the tail
idx++;
} else
body.remove(snake.removeLast()); // move tail