public class SnakeGame {
class Position{
int x;
int y;
public Position(int x,int y){
this.x = x;
this.y = y;
}
public boolean isEqual(Position p){
return this.x==p.x && this.y == p.y ;
}
}
int len;
int rows ,cols;
int[][] food;
LinkedList<Position> snake;
/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
this.rows = height;
this.cols = width;
this.food = food;
snake = new LinkedList<Position>();
snake.add(new Position(0,0));
len = 0; // 最开始吃到的食物为0
}
/** 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. */
public int move(String direction) {
//if(len>=food.length) return len; // 所有的食物都吃完了
Position cur = new Position(snake.get(0).x,snake.get(0).y); // 第一个点是蛇头
switch(direction){ // 蛇头根据方向发生变化
case "U":
cur.x--; break;
case "L":
cur.y--; break;
case "R":
cur.y++; break;
case "D":
cur.x++; break;
}
// 是否越界
if(cur.x<0 || cur.x>= rows || cur.y<0 || cur.y>=cols) return -1;
// 检查cur是否撞到蛇身。蛇尾是要移动的,所以不考虑
for(int i=1; i<snake.size()-1; i++) {
Position next = snake.get(i);
if(next.isEqual(cur)) return -1;
}
snake.addFirst(cur);
// 检查当前点是否是果子
if(len<food.length){
if(cur.x == food[len][0] && cur.y == food[len][1]){ //如果是果子,len++
len++;
}
}
// 调整snake的长度
while(snake.size()>len+1) snake.removeLast();
return len; // len代表game score
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
}
public class SnakeGame {
//2D position info is encoded to 1D and stored as two copies
Set<Integer> set; // this copy is good for fast loop-up for eating body case
Deque<Integer> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
set = new HashSet<>();
set.add(0); //intially at [0][0]
body = new LinkedList<>();
body.offerLast(0);
}
/** 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. */
public int move(String direction) {
//case 0: game already over: do nothing
if (score == -1) {
return -1;
}
// compute new head
int rowHead = body.peekFirst() / width;
int colHead = body.peekFirst() % width;
switch (direction) {
case "U" : rowHead--;
break;
case "D" : rowHead++;
break;
case "L" : colHead--;
break;
default : colHead++;
}
int head = rowHead * width + colHead;
//case 1: out of boundary or eating body
set.remove(body.peekLast()); // new head is legal to be in old tail's position, remove from set temporarily
if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
return score = -1;
}
// add head for case2 and case3
set.add(head);
body.offerFirst(head);
//case2: eating food, keep tail, add head
if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]) {
set.add(body.peekLast()); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
//case3: normal move, remove tail, add head
body.pollLast();
return score;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/