I saw this hard problem in a local Russian contest some time back and I was unable to solve it, Can anybody help?
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...