​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);
 */