Shortest Path in a Grid

You are given a 2D grid with m rows and n columns. Each cell in the grid is either '0' (an empty cell) or '1' (an obstacle). Your task is to find the shortest path from the top-left cell at coordinates \( (0,0) \) to the bottom-right cell at \( (m-1,n-1) \). You are allowed to move in four directions: up, down, left, and right. The movement cost between adjacent cells is 1. If there is no valid path from the start to the destination, output \( -1 \).

Note: The grid is indexed from 0. Both the starting cell and the destination cell must be accessible (i.e. must be '0') for a valid path to exist.

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( T ) denoting the number of test cases. For each test case, the first line contains two integers ( m ) and ( n ) representing the dimensions of the grid. This is followed by ( m ) lines, each containing a string of length ( n ) that represents a row of the grid. Each character in the string is either '0' (empty cell) or '1' (obstacle).

outputFormat

For each test case, print a single integer on a new line representing the length of the shortest path from the top-left cell to the bottom-right cell. If no such path exists, print ( -1 ). The output should be printed on standard output (stdout).## sample

2
3 3
000
010
000
3 3
011
010
110

4
-1