Taco: Grid Shortest Path

You are given a grid represented by N rows and M columns consisting of characters '0' and '1'. The character '0' indicates a free cell, while '1' represents an obstacle. You need to determine the length of the shortest path from a given starting cell to a given destination cell, where you can move in the four primary directions: up, down, left, and right. If no valid path exists, output -1.

The problem can be formally described as follows:

Let \(G\) be a grid of size \(N \times M\). Given a start cell \((x_s,y_s)\) and a destination cell \((x_g,y_g)\), find the minimum number of moves required to reach \((x_g,y_g)\) from \((x_s,y_s)\) while avoiding obstacles. If \(x_s = x_g\) and \(y_s = y_g\), the required distance is 0. Otherwise, if there is no valid path, return -1.

You are expected to use a breadth-first search (BFS) algorithm to solve this problem efficiently.

inputFormat

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

1. The first line contains an integer \(T\) representing the number of test cases.
2. For each test case:
   1. The first line contains two integers \(N\) and \(M\), the number of rows and columns respectively.
   2. The next \(N\) lines each contain a string of length \(M\) representing a row of the grid. Each character is either '0' (a free cell) or '1' (an obstacle).
   3. The following line contains two integers denoting the starting coordinates \(x_s\) and \(y_s\) (0-indexed).
   4. The next line contains two integers denoting the destination coordinates \(x_g\) and \(y_g\) (0-indexed).

outputFormat

For each test case, output a single line in the format:

Case i: d

where \(i\) is the test case number (starting from 1) and \(d\) is the shortest path distance from the start cell to the destination cell. If no valid path exists, output \(-1\).

## sample

5
5 5
00000
01010
00000
01010
00000
0 0
4 4
3 3
010
010
010
0 0
2 2
3 3
000
000
000
0 0
0 1
2 2
00
00
0 0
0 0
2 2
01
11
0 0
1 1

Case 1: 8
Case 2: -1
Case 3: 1
Case 4: 0
Case 5: -1

</p>