353. Design Snake Game

T: O(1)
S: O(mn + food_len)

```java
class SnakeGame {
    private Set<Integer> set;
    private LinkedList<Integer> body;
    private LinkedList<Integer> food;
    private Map<String, int[]> directionMap;
    private int m;
    private int n;

    public SnakeGame(int width, int height, int[][] food) {
        this.m = height;
        this.n = width;
        this.set = new HashSet<>();
        this.set.add(encode(0, 0));
        
        this.body = new LinkedList<>();
        this.body.add(encode(0, 0));

        this.directionMap = new HashMap<>();
        this.directionMap.put("R", new int[] {0, 1});
        this.directionMap.put("L", new int[] {0, -1});
        this.directionMap.put("U", new int[] {-1, 0});
        this.directionMap.put("D", new int[] {1, 0});
        
        this.food = new LinkedList<>();
        for (int[] f : food) {
            this.food.add(encode(f[0], f[1]));
        }
    }
    
    public int move(String direction) {
        int head = body.getFirst();
        int[] dir = directionMap.get(direction);
        int x = head/n + dir[0]; // 5/3 = 1, 4/3 = 1
        int y = head%n + dir[1]; // 2, 1
        int newPositionCode = encode(x, y);
        //System.out.println("setszie"+set.size()+ "," + set.toString());
        //System.out.println("d:"+direction+ ","+x + "," + y);
        if (x < 0 || x >= m || y < 0 || y >= n) { // can't check tail here, because tail is still there
            return -1;
        }

        body.addFirst(newPositionCode);
        if (!food.isEmpty() && newPositionCode == food.getFirst()) {
            food.removeFirst();
        } else {
            int removed = body.removeLast();
            //System.out.println("removed:"+removed);
            set.remove(removed);
        }
        //System.out.println("newPositionCode:"+newPositionCode);
        if (set.contains(newPositionCode)) { // after we remove tail step, we can check the body is hitted by snake itself
            return -1;
        }
        set.add(newPositionCode);

        return body.size() - 1;
    }
    
    private int encode(int x, int y) {
        return x*n + y;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);


1. body: head tail -> if eat food, no need to delete tail , vise versa
2. if this move not hit yourself, then we can add this move to head


T: O(1)
S: O(mn + food_len)


[[3,3,[[2,0],[0,0],[0,2],[2,2]]],

["D"],["D"],["R"],["U"],["U"],["L"],["D"],["R"],["R"],["U"],["L"],["D"]]
        x     x.    x.    x.    x     x     x     x      x
  012 
0  ..   
1  .x  
2     

   ..
    .


// after we remove tail step, we can check the body is hitted by snake itself

ex:
last step-> 
["D"],["D"],["R"],["U"],["U"],["L"],["D"],["R"],["R"],["U"],["L"],["D"]]


   ["L"] , in here set still has set_size=4,[1, 2, 4, 5] means [0,1] [0,2], [1,1], [1,2]

  012    you can see, there is still a 1,1 is mark with ?, in here we haven't check, because if we eat a food, we can keep it
0  ..    if not we will remove it
1  ?.  
2   

to   ["D"]] ok, no food so remove it [1,1] (the last one), so now set become [0,1] [0,2], [1,2](?) the virtual tail
             then we can check is new position [1,1] in set? not in set, so we can add it to set  
  012        then we have new position [1,1], so add it to set again -> become [0,1] [0,2], [1,1], [1,2] again
0  ..   
1  .?  
2   



 */
```