Shortest Path in a Grid

You are given a grid of characters with dimensions \(H \times W\). Each cell is either passable (.) or blocked (#). Your task is to determine the shortest path for a robot to move from a start cell \((r_{start}, c_{start})\) to a target cell \((r_{target}, c_{target})\) using only up, down, left, or right moves. If no such path exists, output -1.

Note: The distance is defined as the number of moves taken. The grid boundaries are defined such that \(0 \leq r < H\) and \(0 \leq c < W\).

The problem may be formulated using the Manhattan distance concept, though obstacles might force a longer route.

inputFormat

The input consists of multiple test cases. Each test case has the following format:

• The first line contains two integers \(H\) and \(W\), representing the number of rows and columns of the grid.
• The second line contains four integers: \(r_{start}\), \(c_{start}\), \(r_{target}\), \(c_{target}\), representing the starting and target positions (0-indexed).
• The next \(H\) lines each contain a string of \(W\) characters. A dot (.) represents a free cell and a hash (#) represents an obstacle.
• A line containing a single 0 indicates the end of input.

Input is provided via standard input.

outputFormat

For each test case, output a single line containing one integer which is the length of the shortest path from the start to the target. If no valid path exists, output -1.

Output is provided via standard output.

5 5
0 0 4 4
.....
.....
..#..
.....
.....
0

8