There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game.
The game proceeds as follows -
- Both players take alternate turns.
- In each turn, the player has to extend the length of the snake by moving it's head in either of the three directions (left/right/forward) by one pixel thereby increasing the length of the snake by 1 pixel. Therefore, the snake doesn't move from it's initial position but only the length of the snake increases and it's head moves in some direction.
- The head of the snake cannot cross it's body or any of the blocked pixels.
- The Player who cannot extend the length of the snake anymore loses the game.
The list of blocked pixels is given to you.
Initially the length of the snake is 1 pixel i.e. it occupies only one pixel from the NxN pixels.
I need to know for each unblocked pixel, who will win the game if Player A starts the game by putting the snake on this particular pixel initially.
I tried reducing the problem to apply the Sprague-Grundy theorem but made no progress as the size of the display is too large (90x90) So, calculating the Grundy numbers for each state isn't computationally feasible.
Also, I suspect that there exists a max flow solution to the problem but I failed to construct the flow network for the given problem.
Can someone suggest a solution which works for the given dimensions of the display?