Snake Game
A snake moves on a board with rows rows and cols columns. It starts as a single cell at [0, 0], the top-left corner. moves is a string of the letters U, D, L and R (up is towards row 0), and on each move the head steps one cell in that direction. Pieces of food appear one at a time at the positions listed in food, in that order: only the first piece not yet eaten is on the board. When the head steps onto that piece, the snake eats it, scores a point and grows by one cell, because its tail stays where it is on that move. On every other move the tail leaves its cell first, so the head may step into the cell the tail is just leaving. The game ends when the head would leave the board, or would step onto a cell that is still part of the snake after the tail has moved. Return [score, steps]: the number of pieces eaten and the number of moves made before the game ended. The move that ends the game does not count, and if the game never ends, steps is len(moves).
Example 1
The snake eats the food at [0, 2] and then the food at [1, 2], growing to three cells, and the last move to the left is safe.
Example 2
The snake eats all four pieces and is five cells long. Moving up would put the head on [0, 1], which is still part of the body even after the tail moves, so the game ends after 4 moves.
Constraints
1 <= rows, cols <= 80 <= len(moves) <= 60, using onlyU,D,LandR0 <= len(food) <= 20, and every piece of food lies on the board- a piece of food never appears on a cell that the snake covers at the moment it appears (so
food[0]is not[0, 0])
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Grids problems
- Spiral FillMedium
- Spiral OrderMedium
- Spiral Out From a CellMedium
- Sudoku Rules CheckMedium
- Turn Every RingMedium
- Zigzag DiagonalsMedium
- Darken the BoardHard
- Flags in OrderHard