Java Solution O(n) for every move, since using Queue to check body position


  • 0
    A
    public class SnakeGame {
        private int width;
        private int height;
        private int currX;
        private int currY;
        private int[][] food;
        private int fi;
        // Need to track body movement
        private Deque<String> snake;
        
        // No need to use actual matrix.
        public SnakeGame(int width, int height, int[][] food) {
            this.width = width;
            this.height = height;
            this.food = food;
            this.snake = new LinkedList<>();
        }
        
        // Snake cannot bite its own body! Need to keep track of body positions
        // If food run out, return final score
        public int move(String direction) {
            if (direction.equals("U")) currY -= 1;
            if (direction.equals("D")) currY += 1;
            if (direction.equals("L")) currX -= 1;
            if (direction.equals("R")) currX += 1;
            
            String coors = currY + "," + currX;
            
            if (currX < 0 || currY < 0 || currX >= width || currY >= height || snake.contains(coors)) return -1;
            
            // move one forward
            snake.addFirst(coors);
            String last = snake.removeLast();
            
            // done all foods
            if (fi >= food.length) return snake.size();
            
            // eat food
            if (food[fi][0] == currY && food[fi][1] == currX) {
                snake.add(last);    // add removed piece due to movement; the extra "food" eaten
                fi++;
            }
            return snake.size();
        }
    

Log in to reply
 

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