Beat 93% 219 ms Use Only One Deque


  • 0
    Q

    Take a look at this crawling deque

    public class SnakeGame {
        int[][] fd;
        int fdIndex, width, height;
        Deque<Integer> snake;
        int score;
        /** 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) {
            this.width = width;
            this.height = height;
            fd = food;
            fdIndex = 0;
            snake = new LinkedList<Integer>();
            snake.offer(0);
            score = 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) {
            char tc = direction.charAt(0);
            if (tc == 'U' || tc == 'L' || tc == 'D' || tc == 'R') {
                int snakeHead = snake.peekFirst();
                int rDif = (tc == 'U') ? -1 : (tc == 'D' ? 1 : 0);
                int cDif = (tc == 'L') ? -1 : (tc == 'R' ? 1 : 0); 
                int tmpR = (snakeHead/width) + rDif, tmpC = (snakeHead%width)+cDif;
                if (tmpR < 0 || tmpR >= height || tmpC < 0 || tmpC >= width) {
                    return -1;
                }
                if (fdIndex < fd.length && tmpR == fd[fdIndex][0] && tmpC == fd[fdIndex][1]) {
                    score++;
                    fdIndex++;
                } else {
                    snake.pollLast();
                }
                if (snake.contains(tmpR*width+tmpC)) {
                    return -1;        
                }
                snake.addFirst(tmpR*width+tmpC);
                return score;
            }
            return -1;
        }
    }

Log in to reply
 

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