LeetCode刷题实战353：贪吃蛇-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 贪吃蛇，我们先来看题面：

https://leetcode-cn.com/problems/design-snake-game/

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0,0) with length = 1 unit.

You are given a list of food's positions in row-column order. When a snake eats the food, its length and the game's score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

请你设计一个贪吃蛇游戏，该游戏将会在一个屏幕尺寸 = 宽度 x 高度的屏幕上运行。如果你不熟悉这个游戏，可以点击这里在线试玩。

起初时，蛇在左上角的 (0, 0) 位置，身体长度为 1 个单位。

你将会被给出一个 (行, 列) 形式的食物位置序列。当蛇吃到食物时，身子的长度会增加 1 个单位，得分也会 +1。

食物不会同时出现，会按列表的顺序逐一显示在屏幕上。比方讲，第一个食物被蛇吃掉后，第二个食物才会出现。

当一个食物在屏幕上出现时，它被保证不能出现在被蛇身体占据的格子里。

对于每个 move() 操作，你需要返回当前得分或 -1（表示蛇与自己身体或墙相撞，意味游戏结束）。

示例

示例：

给定 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 (蛇与边界相撞，游戏结束

解题

https://blog.csdn.net/zshouyi/article/details/73335535

写一个贪吃蛇的程序，每吃到一个food，长度加一，撞墙或者咬到自己会死。这里用queue，和hashset记录目前所占的区域，queue主要负责更新区域，hashset主要负责查看会不会咬到自己。有一点注意的是有时下一步的位移是上一步的结尾，这时肯定是可行的，这时过早往hashset添加head是重复的，待会儿删除时，会把尾巴删掉，刚添加的头因为与尾巴相同，被删掉了，需要记得补回来。代码如下：

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