用 Deque 做。加 Set 可以优化时间，但是加 Set 跑不通不知道哪里有问题。。。
class SnakeGame {
// Set<Integer> set;
Deque<Integer> deque;
int width;
int height;
int[][] foods;
int foodIndex;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.foods = food;
this.foodIndex = 0;
// this.set = new HashSet<>();
// set.add(0);
deque = new ArrayDeque<>();
deque.offerLast(0);
}
public int move(String direction) {
int row = deque.peekFirst() / width;
int col = deque.peekFirst() % width;
if (direction.equals("U")) {
row --;
} else if (direction.equals("D")) {
row ++;
} else if (direction.equals("L")) {
col --;
} else { // direction.equals("R")
col ++;
}
int newHead = row * width + col;
int tail = deque.peekLast();
if (newHead != tail && deque.contains(newHead)) {
return -1;
}
if (row < 0 || row >= height || col < 0 || col >= width) {
return -1;
}
deque.offerFirst(newHead);
// set.add(newHead);
if (foodIndex < foods.length && row == foods[foodIndex][0] && col == foods[foodIndex][1]) {
foodIndex ++;
} else {
int cur = deque.pollLast();
// set.remove(cur);
}
return foodIndex;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/