505. The Maze II

Practice The Maze II for free on NudgeCode: Medium, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

maze is a grid where 0 is an empty cell and 1 is a wall; everything outside the grid counts as wall too. A ball sits at start. You can push it up, down, left or right. Once pushed, it keeps rolling in that direction until the next cell is a wall, and only then stops. After it stops you may push it again in any direction.

The distance of a route is the number of cells the ball rolls past, not counting start but counting the cell it ends on; one push that rolls 3 cells adds 3. Return the shortest distance for the ball to stop at destination, or -1 if it can't stop there. start and destination are [row, col] pairs.

Example

maze = [[0,0,1,0,0],
        [0,0,0,0,0],
        [0,0,0,1,0],
        [1,1,0,1,1],
        [0,0,0,0,0]]
start = [0,4], destination = [4,4]  ->  12
start = [0,4], destination = [3,2]  ->  -1

One shortest route in the first case is left 1, down 1, left 3, down 1, right 2, down 2, right 2: 12 cells in total.

Constraints