Shortest Path in a Maze

Given an \(n \times n\) maze represented as a grid of integers where 0 indicates an empty cell and 1 indicates an obstacle, your task is to find the length of the shortest path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((n-1,n-1)\)). Movement is allowed in four directions: up, down, left, and right. The length of a path is defined as the number of cells visited (including the start and end cells). If the starting or ending cell is blocked or if there is no valid path, output \(-1\).

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains an integer \(n\) (\(1 \le n \le 1000\)), representing the number of rows (and columns) in the maze.
The next \(n\) lines each contain \(n\) space-separated integers (either 0 or 1) representing the maze grid.

outputFormat

Output a single integer to standard output (stdout), representing the length of the shortest path from the top-left corner to the bottom-right corner. If no valid path exists, output \(-1\).

4
0 1 0 0
0 1 0 1
0 0 0 1
1 1 0 0

7