Accepted Java Solution


  • 0
    A

    First, I think the problem needs a few clarification:

    1. The game should somehow guarantee that next food, which is predefined in the array, shall never appear on a cell which happens to be occupied by the snake.
    2. It's OK to "turn back", such as: Head,Tail -> Tail, Head, which means tail moves first, then head.
    3. If all the foods are exhausted, the game will continue, without any food appearing.

    So trick is: use a LinkedList to track the snake; each move, we remove the tail (last element) and add a new head; if the snake eats a food, then tail stays but head extends. Use a set to track the body so if the new head exists in the set, return -1.

    private int width, height;
    int[][] food;
    private int score, idx;
    private Deque<Integer> snake;
    private Set<Integer> body;
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        score = 0;
        idx = 0;
        snake = new LinkedList<>();
        snake.addLast(0);
        body = new HashSet<>();
        body.add(0);
    }
    
    public int move(String direction) {
        // first of all, get head
        int h = snake.getFirst() / width, w = snake.getFirst() % width;
        if (direction.equals("U")) h--;
        else if (direction.equals("D")) h++;
        else if (direction.equals("L")) w--;
        else w++;
        if (w < 0 || w == width || h < 0 || h == height) return -1;
        int head = h*width + w;
        snake.addFirst(head); // move head
        if (idx < food.length && h == food[idx][0] && w == food[idx][1]) {
            score++; // and still keep the tail
            idx++;
        } else
            body.remove(snake.removeLast()); // move tail
        if (!body.add(head)) return -1;
        return score;
    }

  • 0

    For point 2., we have just fixed the test cases such that there's no longer such case as "turning back". So you may consider another approach mentioned by @hong2 here:

    Keep the snake tail before checking body bite. Next if no food to eat, remove the tail.


Log in to reply
 

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