field of size n × n: 0 is an empty cell and 1 is an obstacle. A snake occupies two adjacent cells. It starts lying horizontally on cells (0, 0) and (0, 1) and has to reach the bottom-right corner, lying horizontally on cells (n - 1, n - 2) and (n - 1, n - 1).
In one move the snake can:
- slide one cell right, if both cells it moves onto are empty (its orientation stays the same);
- slide one cell down, under the same condition;
- if it lies horizontally on (r, c) and (r, c + 1) and both cells below it are empty, turn clockwise around (r, c) to stand vertically on (r, c) and (r + 1, c);
- if it stands vertically on (r, c) and (r + 1, c) and both cells to its right are empty, turn counterclockwise around (r, c) to lie horizontally on (r, c) and (r, c + 1).
Return the fewest moves to reach the goal, or -1 if it cannot be reached.field=[[0, 0, 0], [0, 0, 0], [0, 0, 0]] → 3
The snake slides down twice and right once: 3 moves.
field=[[0, 0, 1], [1, 0, 0], [1, 0, 0]] → -1
Cell (0, 2) to the right is a wall and so is cell (1, 0) under the tail: the snake can neither slide right, slide down nor turn. The answer is -1.
field=[[0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0]] → 5
(0, 0) and (0, 1) are emptyfield=[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
3
Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.