Share my easy java solution


  • 16
    J

    public class SnakeGame {

        class Position{
            int x;
            int y;
            public Position(int x,int y){
                this.x = x;
                this.y = y;
            }
            public boolean isEqual(Position p){
                return this.x==p.x && this.y == p.y ;
            }
        }
        int len;
        int rows ,cols;
        
        int[][] food;
        LinkedList<Position> snake;
       
        /** 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.rows = height;
            this.cols = width;
            this.food = food;
       
            snake = new LinkedList<Position>();
            snake.add(new Position(0,0));
            len = 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) {
        	//if(len>=food.length) return len;
        
            Position cur = new Position(snake.get(0).x,snake.get(0).y);
            
            switch(direction){
            case "U": 
                cur.x--;  break;
            case "L": 
                cur.y--; break;
            case "R": 
                cur.y++;   break;
            case "D": 
                cur.x++;   break;
            }
            
            if(cur.x<0 || cur.x>= rows || cur.y<0 || cur.y>=cols) return -1;
            
    
            for(int i=1;i<snake.size()-1;i++){
                Position next = snake.get(i);
                if(next.isEqual(cur)) return -1;	       
            }
            snake.addFirst(cur);     
            if(len<food.length){
                Position p = new Position(food[len][0],food[len][1]);	        
                if(cur.isEqual(p)){	            
                    len++;
                }
            }
            while(snake.size()>len+1) snake.removeLast();
           
            return len;
        }
    
    
    /**
     * Your SnakeGame object will be instantiated and called as such:
     * SnakeGame obj = new SnakeGame(width, height, food);
     * int param_1 = obj.move(direction);
     */
    

    }


  • 0
    M

    Straightforward and clear solution!
    Vote up


  • 0
    M

    thanks for sharing.
    but in the move() method,
    why "for(int i=1;i<snake.size()-1;i++)", while checking if the snake will bite itself.
    why skip the last cell.

    and, why the last "while(snake.size()>len+1) snake.removeLast();" is necessary, why is it needed to control the length of the snake?


  • 0
    S

    Thanks for shareing. Upvoted. The last while loop can be changed to if statement. if(snake.size()>len+1) snake.removeLast(); The reason is, the move() is invoked step by step. But I still wonder why it is (> len + 1)? why add 1?


  • 0
    S

    @mycoy In my understanding, the last cell will be moved anyway, so no need to check this point. The head is also not needed, as head cannot bite head itself. For the removeLast(), whenever move() invoked, a new head is added to snake, snake.addFirst(cur); We may need to remove the tail, which depends on if it got food in current cell. If it got food, just add head, and no remove required. If not, need to remove the tail.


  • 0
    A

    @mycoy From my understanding, it is the first cell that is being skipped.
    For example. Assume that the moves are in consecutive order : {"R","D","R","U","L","D","L","U","R"}; and the food locations are at : {{1,2},{0,1},{1,1},{1,0}}. In that case, when you are in the second last move, The body of the snake will be occupied in head = [0,0], followed by [1,0],[1,1],[0,1],[0,2]. The length being so much because it has already consumed the food in all the positions by then. So now, when you have the last move "R", you are moving to cell [0,1] and when you are moving to cell [0,1] , by no means can you bite [0,0],[1,0],[1,1]. In other words, the min length of the snake has to be 4 in order to bite itself. As a result, we can skip the first element , which in this case would be [0,0]. I think it should be okay to start the loop from 3 also. Correct me if I am wrong.


  • 0
    A

    @shileiwill From my understanding, that is because the length of the snake is originally assumed to be 1(even before it consumes any food).


  • 0
    M

    Great solution.
    One thing you can improve is to use HashSet to check if there is a collision. When the snake grows, the check will be expensive. ~O(n)

    Now some effort should be taken care of to use HashSet for Objects such as points.
    Anyway, it is a great solution.


Log in to reply
 

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