LeetCode刷题实战353:贪吃蛇
示例
示例:
给定 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); */
赞 (0)