Runtime beats 96.49% Java simple linked list solution


  • 0
    A
    public class SnakeGame {
        class Unit {
            int r;
            int c;
            Unit next;
            
            Unit(int r, int c) {
                this.r = r;
                this.c = c;
                this.next = null;
            }
            
            void move(int x, int y) {
                if (next != null)
                    next.move(r, c);
                r = x;
                c = y;
            }
        }
        
        int width;
        int height;
        int[][] food;
        int foodIndex;
        int score;
        Unit head;
        
        /** 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;
            this.food = food;
            this.foodIndex = 0;
            this.score = 0;
            this.head = new Unit(0, 0);
        }
        
        void setHead(int x, int y) {
            Unit new_head = new Unit(x, y);
            new_head.next = head;
            head = new_head;
        }
        
        boolean isTouchingItself(int x, int y) {
            Unit temp = head.next;
            while (temp != null && temp.next != null) {
                if (temp.r == x && temp.c == y)
                    return true;
                temp = temp.next;
            }
            return false;
        }
    
        /** 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) {
            int new_r = head.r;
            int new_c = head.c;
            if (direction.equals("U"))
                new_r -= 1;
            else if (direction.equals("D"))
                new_r += 1;
            else if (direction.equals("L"))
                new_c -= 1;
            else if (direction.equals("R"))
                new_c += 1;
            if (new_r < 0 || new_c < 0 || new_r >= height || new_c >= width || isTouchingItself(new_r, new_c))
                return -1;
                
            if (foodIndex < food.length && new_r == food[foodIndex][0] && new_c == food[foodIndex][1]) {
                setHead(new_r, new_c);
                score++;
                foodIndex++;
            } else
                head.move(new_r, new_c);
            return score;
        }
    }
    
    /**
     * Your SnakeGame object will be instantiated and called as such:
     * SnakeGame obj = new SnakeGame(width, height, food);
     * int param_1 = obj.move(direction);
     */
    

Log in to reply
 

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