Concise Java LinkedList+HashSet solution


  • 0
    public class SnakeGame {
    
        class T {
            int r;
            int c;
            public T(int r, int c) {
                this.r = r;
                this.c = c;
            }
            public boolean equals(T t) {
                return r==t.r && c==t.c;
            }
        }
        
        Set<Integer> covers;
        LinkedList<T> snake;
        Map<Character,T> dirMap;
        
        int width;
        int height;
        int[][] food;
        int foodIdx;
        int score;
    
        public SnakeGame(int width, int height, int[][] food) {
            covers = new HashSet<>();
            snake = new LinkedList<>();
            snake.add(new T(0,0));
            covers.add(0);
            
            this.width = width;
            this.height = height;
            this.food = food;
            foodIdx = 0;
            score = 0;
            
            dirMap = new HashMap<>();
            dirMap.put('U', new T(-1,0));
            dirMap.put('L', new T(0,-1));
            dirMap.put('R', new T(0,1));
            dirMap.put('D', new T(1,0));
        }
        
        private T getNextPos(T pos, char dir) {
            return new T(pos.r+dirMap.get(dir).r, pos.c+dirMap.get(dir).c);
        }
        
        public int move(String direction) {
            if(direction.isEmpty())
                return score;
            for(char dir : direction.toCharArray()) {
                T head = snake.getFirst();
                T newHead = getNextPos(head, dir);
                if(newHead.r<0 || newHead.r>=height || newHead.c<0 || newHead.c>=width)
                    return -1;
                if(!newHead.equals(snake.peekLast()) && covers.contains(newHead.r*width+newHead.c))
                    return -1;
                if(foodIdx<food.length && food[foodIdx][0]==newHead.r && food[foodIdx][1]==newHead.c) {
                    snake.offerFirst(newHead);
                    covers.add(newHead.r*width+newHead.c);
                    foodIdx++;
                    score++;
                } else { // move the snake
                    T tail = snake.pollLast();
                    covers.remove(tail.r*width+tail.c);
                    snake.offerFirst(newHead);
                    covers.add(newHead.r*width+newHead.c);
                }
            }
            return score;
        }
    }

Log in to reply
 

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