LeetCode刷题实战353:贪吃蛇
共 7377字,需浏览 15分钟
·
2021-08-20 00:02
示例
示例:
给定 width = 3, height = 2, 食物序列为 food = [[1,2],[0,1]]。
Snake snake = new Snake(width, height, food);
初始时,蛇的位置在 (0,0) 且第一个食物在 (1,2)。
|S| | |
| | |F|
snake.move("R"); -> 函数返回 0
| |S| |
| | |F|
snake.move("D"); -> 函数返回 0
| | | |
| |S|F|
snake.move("R"); -> 函数返回 1
(蛇吃掉了第一个食物,同时第二个食物出现在位置 (0,1))
| |F| |
| |S|S|
snake.move("U"); -> 函数返回 1
| |F|S|
| | |S|
snake.move("L"); -> 函数返回 2 (蛇吃掉了第二个食物)
| |S|S|
| | |S|
snake.move("U"); -> 函数返回 -1 (蛇与边界相撞,游戏结束
解题
public class SnakeGame {
Queue<Integer> queue = new LinkedList<Integer>();
HashSet<Integer> hs = new HashSet<Integer>();
int[][] foods;
int foodIndex;
int width, height;
int currRow, currCol;
/** 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) {
queue.offer(0);
hs.add(0);
this.foods = food;
this.foodIndex = 0;
this.width = width;
this.height = height;
currRow = 0;
currCol = 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 (direction.equals("U")) {
currRow --;
} else if (direction.equals("D")) {
currRow ++;
} else if (direction.equals("L")) {
currCol --;
} else if (direction.equals("R")) {
currCol ++;
}
int head = currRow * width + currCol;
/*System.out.print(direction);
System.out.print(head);
System.out.println(queue.peek());
System.out.println(hs);*/
if (head != queue.peek() && hs.contains(head)) {
return -1;
}
if (currRow >= 0 && currRow < height && currCol >= 0 && currCol < width) {
queue.offer(head);
hs.add(head);
if (foodIndex < foods.length && currRow == foods[foodIndex][0] && currCol == foods[foodIndex][1]) {
foodIndex ++;
} else {
int trail = queue.poll();
hs.remove(trail);
if (head == trail)
hs.add(head);
}
return foodIndex;
}
return -1;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/