Maze Navigation: Shortest Path in a Grid

You are given an M×N grid representing a maze. Each cell in the maze can either be empty (denoted by 0) or blocked (denoted by 1). The task is to compute the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (M-1, N-1)) using only four possible directions of movement: up, down, left, and right.

If a path exists, output the minimum number of moves needed. Otherwise, output -1.

The solution typically employs a breadth-first search (BFS) algorithm, which systematically explores the maze level by level. The correctness of the approach can be summarized by the following condition: if we denote by \(d(i,j)\) the distance (in moves) to cell \((i,j)\) from the start, then for every movement from \((i,j)\) to a valid adjacent cell \((i',j')\), it must hold that \(d(i',j') = d(i,j) + 1\).

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
M N
row1
row2
...
rowM

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers M and N separated by a space.
• This is followed by M lines, each containing N integers (each either 0 or 1) separated by spaces, representing the maze grid.

outputFormat

For each test case, output a single integer on a new line, representing the shortest number of moves required to reach the bottom-right corner from the top-left corner. If no valid path exists, output -1.

## sample

1
1 1
0

0

</p>