Shortest Safe Route in a Field Problem Statement

Ninja wants to cross a field represented as a rectangular matrix of size M x N, containing landmines. A landmine gets triggered if a person is within one cell of its placement, thus Ninja must avoid not only the mines but also the four adjacent cells (left, right, above, and below).

Your task is to determine the length of the shortest safe route from any cell in the first column to any cell in the last column of the matrix.

Example:

Input:

Field size: 4 x 4
Field Matrix: 
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1

Output:

3

Explanation:

The safe route avoids landmines (0 in matrix) and unsafe adjacent cells. The shortest path marked allows Ninja to move through the field in 3 steps.

Constraints:

• 1 <= T <= 10
• 1 <= M, N <= 1000
• 0 <= Field[i][j] <= 1
• Time Limit: 1 sec

Input:

Number of test cases: T
For each test case:
- Two integers M and N
- M lines each containing N integers (0 or 1)

Output:

For each test case, output the length of the shortest safe route or -1 if no such path exists.

Note:

The path length is the number of steps, not the number of cells in the path.