Shortest Path on Grid

You are given a grid with dimensions (m \times n) where each cell is either passable (denoted by 1) or impassable (denoted by 0). A robot is placed at a starting coordinate and needs to reach a destination coordinate. The robot can move only in four directions: up, down, left, and right. Your task is to determine the length of the shortest path from the start to the destination using a Breadth-First Search (BFS) algorithm. If no valid path exists, output "No path".

Note: The grid, starting point, and destination are provided as input, and the answer must be output in a specific format including the test case number.

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing two integers (m) and (n) (the numbers of rows and columns). This is followed by (m) lines, each containing (n) integers (either 0 or 1) representing the grid. Next, there is a line with four integers: (sx), (sy), (dx), and (dy) representing the starting and destination coordinates, respectively. The input terminates with a line containing "0 0".

outputFormat

For each test case, output a single line in the format "<case_number> ", where <case_number> is the sequential test case number (starting from 1) and is the length of the shortest path if it exists, or "No path" if there is no valid path.## sample

5 5
1 1 1 0 1
1 0 1 1 1
1 0 0 1 1
1 1 1 0 1
1 1 1 1 1
0 0 4 4
4 4
1 1 0 1
1 0 1 1
0 1 1 1
1 1 1 0
0 0 3 3
2 2
1 1
1 1
0 0 0 1
0 0

1 8
2 No path
3 1