贪食蛇。
GAME OVER有2种情况，1是咬到自己，2是出界。
1）用QUEUE来保留占据的格子，每走一格就添加1个，然后POll()最后一个。 做一个一样的SET来check要走的格子是不是已经在自己身体里。这里需要注意用int[2]来加到SET里是不行的。。开始怀念C的指针了。 我们用一个比较典型的HASH来通过一个整数记录位置。
比如高是4，那么高的INDEX是0-3，不会超过4。对于一个点M,N来说，HASH最后的结果就是m*高 + n，这样不会有collision。。
2）出界比较好判断，知道当前要走的位置就行。。
GAME MOVE ON就是看吃豆(或者吃屎）的问题，用INDEX记录当前的豆，刷新的时候还要判断一次新豆在不在自己身体的SET里。
剩下的就是edge cases，比如要先POLL出再看能不能咬到自己；比如能吃的都吃了该怎么办，题里没说，但是看TEST CASE的意思是吃光了就不吃了。。但是游戏继续。
public class SnakeGame {
/** 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]. */
// boundry
int w;
int h;
// cur location
int m;
int n;
// food
int index;
int[][] f;
Set<Integer> set;
Queue<Integer> q;
public SnakeGame(int width, int height, int[][] food)
{
m = 0;
n = 0;
w = width;
h = height;
set = new HashSet<Integer>();
q = new LinkedList<Integer>();
set.add(0);
q.add(0);
f = food;
index = 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("R") && n == w-1) || (direction.equals("L") && n == 0) ||
(direction.equals("U") && m == 0) || (direction.equals("D") && m == h-1)) return -1;
if(direction.equals("R"))
{
n++;
}
else if(direction.equals("L"))
{
n--;
}
else if(direction.equals("U"))
{
m--;
}
else if(direction.equals("D"))
{
m++;
}
if(index < f.length && m == f[index][0] && n == f[index][1])
{
index++;
while(index < f.length && eatself(f[index][0],f[index][1])) index++;
}
else
{
set.remove(q.poll());
if(eatself(m,n)) return -1;
}
int temp = m*w + n;
q.add(temp);
set.add(temp);
return set.size()-1;
}
public boolean eatself(int x, int y)
{
return set.contains(x*w+y);
}
}
/*
["SnakeGame","move","move","move","move","move","move"]
[[3,2,[[1,2],[0,1]]],["R"],["D"],["R"],["U"],["L"],["U"]]
["SnakeGame","move","move","move","move","move","move","move","move","move","move","move","move"]
[[3,3,[[2,0],[0,0],[0,2],[2,2]]],["D"],["D"],["R"],["U"],["U"],["L"],["D"],["R"],["R"],["U"],["L"],["D"]]
["SnakeGame","move","move"]
[[2,2,[[0,1]]],["R"],["D"]]
["SnakeGame","move","move","move","move","move","move","move","move","move","move","move","move","move","move","move"]
[[3,3,[[2,0],[0,0],[0,2],[0,1],[2,2],[0,1]]],["D"],["D"],["R"],["U"],["U"],["L"],["D"],["R"],["R"],["U"],["L"],["L"],["D"],["R"],["U"]]
*/
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
跌跌撞撞，错了好几次……考虑不周。