Shortest Path in a Grid

You are given one or more grids representing maps. Each grid is defined by its dimensions N (number of rows) and M (number of columns) and contains cells with values either 0 or 1. A cell with a value of 0 is traversable, while a cell with a value of 1 is blocked.

Your task is to determine the length of the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (N-1, M-1)) of each grid. You may only move in four directions: up, down, left, or right. The distance is counted as the number of moves. If there is no valid path, output -1.

The problem can be formulated using the following notation: \[ \text{Let } grid \text{ be a matrix of size } N\times M. \text{ Find the minimum number of moves } d \]

inputFormat

The input is given via standard input and follows the format below:

T
N1 M1
grid[0][0] grid[0][1] ... grid[0][M1-1]
...
grid[N1-1][0] ... grid[N1-1][M1-1]
N2 M2
... (grid for test case 2)
...

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers N and M.
• The following N lines each contain M integers (either 0 or 1) representing the grid.

outputFormat

For each test case, output a single line to standard output containing the minimum number of moves in the shortest path. If no valid path exists, output -1.

1
3 3
0 0 1
0 1 0
0 0 0

4