Maze Escape 2

Problem

Write a function solution that returns the minimum number of moves required to travel from (1, 1) to (n, n) in an ( n \times n ) maze represented by the parameter maze, where the width and height of the maze are both n.

Assume that it is not possible to move outside the bounds of the given maze maze.
Also, assume that the given maze maze always allows for a path from (1, 1) to (n, n).

Constraints

• The maze is given as an ( n \times n ) square grid where the width and height are natural numbers between 3 and 1,000 inclusive.
• All elements of maze are either 0 (passage) or 1 (wall).
  • 0 (passage) represents a traversable path in the maze.
  • 1 (wall) represents an impassable obstacle in the maze.
  • The element (1, 1) in the first row and first column and the element (n, n) in the ( n )-th row and ( n )-th column will always be 0.

Example Test Cases Explanation

Explanation for Test Case 1

• The shortest path from (1,1) to (3,3) is as follows, requiring a total of 4 moves:
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (2,2) $\rightarrow$ (3,2) $\rightarrow$ (3,3)

Explanation for Test Case 2

• The shortest path from (1,1) to (4,4) is as follows, requiring a total of 6 moves:
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (2,2) $\rightarrow$ (3,2) $\rightarrow$ (3,3) $\rightarrow$ (3,4) $\rightarrow$ (4,4)

Explanation for Test Case 3

• The shortest path from (1,1) to (5,5) is as follows, requiring a total of 16 moves:
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (1,3) $\rightarrow$ (1,4) $\rightarrow$ (1,5) $\rightarrow$ (2,5) $\rightarrow$ (3,5) $\rightarrow$ (3,4) $\rightarrow$ (3,3) $\rightarrow$ (3,2) $\rightarrow$ (3,1) $\rightarrow$ (4,1) $\rightarrow$ (5,1) $\rightarrow$ (5,2) $\rightarrow$ (5,3) $\rightarrow$ (5,4) $\rightarrow$ (5,5)