# Snake Game: Minimum Moves to Reach the Apple You are simulating the classic Snake game on a grid with `R` rows and `C` columns. Cells are identified as `(r, c)` with `0 <= r < R` and `0 <= c < C`. The snake is a sequence of `L` distinct cells `body[0], body[1], ..., body[L-1]`, where `body[0]` is the head and every pair of consecutive cells is adjacent (shares an edge). A single apple is located at cell `apple = (ar, ac)`, which is guaranteed not to lie on the snake. ## Movement rules On each move you choose one of the four directions — up, down, left, or right — and the game advances one tick: 1. The new head cell `h'` is the current head shifted one cell in the chosen direction. 2. If `h'` is the apple cell, the snake **eats and grows**: `h'` is prepended to the body and the tail stays in place (length becomes `L + 1`). 3. Otherwise, `h'` is prepended and the tail cell `body[L-1]` is vacated on the same tick (length is unchanged). 4. The move is **legal** only if `h'` is inside the grid and `h'` does not collide with the snake's body as it exists **after** the tail update. Concretely, `h'` must not equal any of `body[0..L-2]`; moving into the current tail cell `body[L-1]` **is** legal on a non-eating move, because the tail vacates that cell during the same tick. The snake cannot pass through walls or through itself, and only ever moves one cell per tick. ## Task Return the minimum number of moves needed for the snake's head to reach the apple cell (the move on which the head enters the apple cell counts), or `-1` if the apple can never be reached by any sequence of legal moves. ## Examples **Example 1** ``` Input: R = 2, C = 3, body = [[0, 0]], apple = [1, 2] Output: 3 ``` A length-1 snake needs 3 moves, e.g. right, right, down. **Example 2** ``` Input: R = 3, C = 3, body = [[0, 2], [0, 1], [0, 0]], apple = [2, 0] Output: 4 ``` One optimal route for the head: down to `(1, 2)`, down to `(2, 2)`, left to `(2, 1)`, left to `(2, 0)`. The body follows the head, vacating one tail cell per tick. **Example 3** ``` Input: R = 2, C = 2, body = [[0, 0], [0, 1], [1, 1]], apple = [1, 0] Output: 1 ``` Moving down puts the head on the apple immediately; the tail does not move on the eating tick. ## Constraints - `2 <= R, C <= 10` - `1 <= L <= min(8, R * C - 1)` - The initial body cells are distinct, consecutive cells are adjacent, and the apple is not on the body.