Straightforward and simple Java solution using Deque.


  • 0
    D

    The basic idea is using a Deque to represent the snake. Regular movements can be expressed as enqueue first and dequeue last. If ate a food, then skip the dequeue. Haven't optimize it, suggestions are welcome.

    private int width, height, x, y;
    private int[][] food;
    private Map<String, int[]> dirs;
    private Deque<Integer> snake;
    
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        dirs = new HashMap<>();
        dirs.put("U", new int[]{0, -1});
        dirs.put("L", new int[]{-1, 0});
        dirs.put("R", new int[]{1, 0});
        dirs.put("D", new int[]{0, 1});
        snake = new ArrayDeque<>();
    }
    
    public int move(String direction) {
        int[] dir = dirs.get(direction);
        if (snake.isEmpty()) {
            x += dir[0];
            y += dir[1];
        } else {
            int head = snake.peekFirst();
            x = head % width + dir[0];
            y = head / width + dir[1];
        }
        int newPos = y * width + x;
        if (x < 0 || x >= width || y < 0 || y >= height || // hit border
            snake.contains(newPos) || // hit body
            (!snake.isEmpty() && snake.peekLast().equals(newPos))) { // hit tail
            return -1;
        }
        boolean ate = false;
        if (snake.size() < food.length && 
            x == food[snake.size()][1] && y == food[snake.size()][0]) {
                ate = true;
        }
        snake.offerFirst(newPos);
        if (!ate) snake.pollLast();
        return snake.size();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.