10k

353. Design Snake Game

Published on

Question

Design the initialization board for the snake game, where the food appears, and the move function. The move function needs to determine if it is losing or scoring after each move and return the score, or -1 (if it is losing).

Algorithm

This topic started with the idea of how to save the whole snake, using an array list, and then ran through the case and found that each step he took was actually removing the tail and adding a new head.

The key point is to choose the right data structure. Because we want to do the increase and decrease operations in the head and tail, deque seems to be a good choice.

There are actually three cases for each step.

  1. normally go to the next step, in this case there are also two cases

    1. did not eat the food (score), corresponding to the head to add a new point, the tail ** do not need to ** remove a point
    2. eat food, corresponding to the head to add a new point, the tail to remove a point

  2. hitting the wall, corresponding to the new head of yes the index is beyond the range of m*n.

  3. hit his body, corresponding to the new head or the next location to go, which exists at a point on the body of the gluttonous snake.

    There is a small pitfall in this place, also I am not familiar enough with deque, then do the judgment, deque's contains does not determine whether an array exists in it, which is the reason I finally implemented a myContains method.

But I ended up with more than enough space in this code, and I'm not quite sure why ...... so I'm posting this answer on leetcode to see if others can give some input.

code

class SnakeGame {
    int[][] board;
    Deque<int[]> snake;
    // score is queue.size - 1;
    Queue<int[]> queue;

    public SnakeGame(int width, int height, int[][] food) {
        board = new int[width][height];
        snake = new LinkedList<>();
        snake.offer(new int[]{0, 0});
        queue = new LinkedList<>();

        for (int[] fo : food) {
            queue.offer(fo);
        }
    }
    
    public int move(String direction) {
        int[] head = snake.peek();
    
        switch (direction) {
            case "R":
                return validNext(head, new int[]{head[0], head[1] + 1});
            case "L":
                return validNext(head, new int[]{head[0], head[1] - 1});
            case "U":
                return validNext(head, new int[]{head[0] - 1, head[1]});
            case "D":
                return validNext(head, new int[]{head[0] + 1, head[1]});
        }        
        return -1;
    }
    
    private int validNext(int[] head, int[] nextHead) {
        int m = board.length;
        int n = board[0].length;
        
        if (nextHead[0] < n && nextHead[0] >= 0 && nextHead[1] >= 0 && nextHead[1] < m) { // not hit wall
            int[] food;
            if (!queue.isEmpty()) { // there are food to show
                food = queue.peek();
            } else {
                food = new int[]{-1, -1};
            }
            if (nextHead[0] ! = food[0] || nextHead[1] ! = food[1]) { // no food on next step
                    snake.pollLast(); // remove tail
                } else {
                    queue.poll();
                }
            if (snake.size() < 4 || !myContains(snake, nextHead)) { // not hit body
                snake.offerFirst(nextHead);
                return snake.size() - 1;
            }
        } 
        return -1; // hit the wall or hit the body
    }
    
    private boolean myContains(Deque<int[]> snake, int[] nextHead) {
        for (int[] body : snake) {
            if (nextHead[0] == body[0] && nextHead[1] == body[1]) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

问题

设计贪吃蛇游戏的初始化棋盘，出现食物的地方，以及move函数，move函数需要判断每次走一步之后是否是输掉或者是得分，返回分数，或者-1（如果输了）。

算法

这个题目一开始想的是如何去保存整个贪吃蛇，用一个数组list，然后跑了一遍case发现，他每走一步其实就是去掉尾巴，新增一个头部。

关键点在于，选择合适的数据结构。因为我们要在头尾做增减操作，deque似乎是个不错的选择。

每走一步其实有三种情况：

  1. 正常的走到了下一步，这种情况下也有两个情况

    1. 没吃到食物（分数），对应头部新增一个点，尾巴不需要去掉一点，
    2. 吃到食物，对应头部新增一个点，尾巴去掉一点

  2. 撞墙，对应是的新的头部的index超出了m*n的范围；

  3. 撞到自己的身体，对应新的头部或者说下一个要走的位置，存在于贪吃蛇的身体上的某个点。

    这个地方有个小坑，也是自己不够熟悉deque，再做判断的时候，deque的contains并不能判断一个数组是否存在其中，这也是我最后实现了一个myContains方法的原因。

不过最终我这个代码空间超过了，我不太清楚为啥……所以我post这个答案在leetcode上看其他人是否可以给些意见。

代码

class SnakeGame {
    int[][] board;
    Deque<int[]> snake;
    // score is queue.size - 1;
    Queue<int[]> queue;

    public SnakeGame(int width, int height, int[][] food) {
        board = new int[width][height];
        snake = new LinkedList<>();
        snake.offer(new int[]{0, 0});
        queue = new LinkedList<>();

        for (int[] fo : food) {
            queue.offer(fo);
        }
    }
    
    public int move(String direction) {
        int[] head = snake.peek();
    
        switch (direction) {
            case "R":
                return validNext(head, new int[]{head[0], head[1] + 1});
            case "L":
                return validNext(head, new int[]{head[0], head[1] - 1});
            case "U":
                return validNext(head, new int[]{head[0] - 1, head[1]});
            case "D":
                return validNext(head, new int[]{head[0] + 1, head[1]});
        }        
        return -1;
    }
    
    private int validNext(int[] head, int[] nextHead) {
        int m = board.length;
        int n = board[0].length;
        
        if (nextHead[0] < n && nextHead[0] >= 0 && nextHead[1] >= 0 && nextHead[1] < m) { //  not hit wall
            int[] food;
            if (!queue.isEmpty()) { // there are food to show
                food = queue.peek();
            } else {
                food = new int[]{-1, -1};
            }
            if (nextHead[0] != food[0] || nextHead[1] != food[1]) { // no food on next step
                    snake.pollLast(); // remove tail
                } else {
                    queue.poll();
                }
            if (snake.size() < 4 || !myContains(snake, nextHead)) { // not hit body
                snake.offerFirst(nextHead);
                return snake.size() - 1;
            }
        } 
        return -1; // hit wall or hit body
    }
    
    private boolean myContains(Deque<int[]> snake, int[] nextHead) {
        for (int[] body : snake) {
            if (nextHead[0] == body[0] && nextHead[1] == body[1]) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */
Thoughts? Leave a comment