Clockwork Gates

Medium · graph traversal

A clockwork garden is a rectangular grid of cells. Each cell of grid holds one number:

-1 is a hedge. Nobody can enter it.
0 is a path that is always open.
2, 3 or 4 is a gate that opens on a regular beat. A gate with number k is open during minute t exactly when t is a multiple of k, and shut otherwise.

A visitor starts on the top-left cell at minute 0 and wants to reach the bottom-right cell. Both of those cells are paths.

Each minute the visitor either stays where they are or moves to a neighbouring cell (up, down, left or right) that is not a hedge. A move that ends in minute t may enter a gate cell only if that gate is open during minute t. Standing still is always allowed, even on a gate that has just shut.

Return the smallest minute at which the visitor can be on the bottom-right cell, or -1 if that never happens.

Examples

Example 1

Input: grid = [[0, 2, 0]]

Output: 3

The gate is shut in minute 1, so the visitor waits a minute, enters it in minute 2 and reaches the end in minute 3.

Example 2

Input: grid = [[0, 3, 0], [0, -1, 0]]

Output: 5

The hedge blocks the lower route, so the visitor must use the gate, which is open only in minute 3. After waiting two minutes they need two more moves.

Example 3

Input: grid = [[0, -1], [-1, 0]]

Output: -1

The hedges cut the visitor off from the goal.

Constraints

1 <= rows, cols <= 25
Every cell is -1, 0, 2, 3 or 4.
The top-left and bottom-right cells are 0.
All rows have the same length.