Java 300ms solution using 2 Queues with explanation. (Different from using Hashset, longer code but save some space)


  • 0

    I have read some other solutions like using Deque and HashSet after I have done this solution. These solutions are cool since they are more concise than this one and you only need take care of the head. But for this one, you do not need to trail the entire body of the snake. But the trade-off is to handle the tail.
    My idea is to use a queue to memorize the point which the snake turns. To check if the snake eat itself, I need go through the turns queue checking if the head after the move has any intersection with the line between 2 turning corners (need to check the new tail and the last turning corner first). To realize that function, I also need to know the moving direction of the tail which "taildirect" will compute it.

    public class SnakeGame {
    int width;
    int height;
    Queue<int[]> food;
    Queue<int[]> turns;
    String currdirect;
    int[] head;
    int[] tail;
    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;
        this.food = new LinkedList<int[]>();
        for(int[] temp:food){
            this.food.offer(temp);
        }
        head = new int[2];
        tail = new int[2];
        currdirect = new String(" ");
        turns = new LinkedList<int[]>();
        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) {
        if(direction.equals(currdirect)!=true&&score>0){
            int[] oldhead = new int[2];
            oldhead[0] = head[0];
            oldhead[1] = head[1];
            turns.offer(oldhead);
        }
    //get new head position
        if(direction.equals("U")) head[0] -= 1;
        else if(direction.equals("L")) head[1] -= 1;
        else if(direction.equals("D")) head[0] += 1;
        else head[1] += 1;//"R"
    //get new tail position    
    //if eat a food,tail position does not change
        boolean eatornot = true;//a flag of eat food or not
    //if not, check the tail's moving direction
        if(eat(head[0],head[1])==false){
            eatornot = false;
            if(taildirect(direction).equals("U")) tail[0] -= 1;
            else if(taildirect(direction).equals("L")) tail[1] -= 1;
            else if(taildirect(direction).equals("D")) tail[0] += 1;
            else tail[1] += 1;//"R"
            //if tail reaches the last turning point, remove it from the turns queue(only need to be checked if tail moves)
            if(turns.peek()!=null&&tail[0] == turns.peek()[0]&&tail[1]==turns.peek()[1]) turns.poll();
        }
    //see if the new positions of head and tail causes death    
        if(alive(head[0],head[1],tail[0],tail[1])==true){
            if(eatornot==true) score++;
        }
        else{
            score = -1;
        }
        currdirect = direction;
        return score;
    
    }
    private String taildirect(String direction){//get the current tail moving direction 
        if(turns.peek()==null||score == 0){//no turns or the length of the snake is 1;
            return direction;
        }
        else{
            int tx, ty;
            String tdirect = new String();
            ty = turns.peek()[0];
            tx = turns.peek()[1];
            if(ty<tail[0]) tdirect = "U";
            else if(ty>tail[0]) tdirect = "D";
            else if(tx<tail[1]) tdirect = "L";
            else tdirect = "R";
            return tdirect;
        }
    }
    private boolean eat(int y, int x){//eat or not after this move
        if(food.peek()==null) return false;
        int food_y = food.peek()[0];
        int food_x = food.peek()[1];
        if(food_y==y&&food_x==x){
            food.poll();
            return true;
        }
        return false;
    }
    private boolean alive(int nhy,int nhx, int nty,int ntx){//dead or alive after the move, newheady, newheadx, new taily, newtailx
    //check if hit the walls
        if(nhy<0||nhy>=height||nhx<0||nhx>=width) return false;
    //check if eat itself(compare the new positions)
        if(turns.peek()==null) return true;
        else{
            int last_x = ntx;
            int last_y = nty;
            Iterator<int[]> iter = turns.iterator();
            for (int[] curr: turns){
                int current_y = curr[0];
                int current_x = curr[1];
                if(nhy==last_y&&(nhx-last_x)*(nhx-current_x)<=0) return false;//check if the newhead hits its body
                if(nhx==last_x&&(nhy-last_y)*(nhy-current_y)<=0) return false;
                last_x = current_x;
                last_y = current_y;
            }
        }
        return true;
    }
    }

Log in to reply
 

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