Minimum Steps to Goal in a Grid

You are given an (N \times M) grid, where each cell is either empty (represented by a dot '.') or blocked by an obstacle (represented by a hash '#'). A creature located at a starting cell ((s_x, s_y)) must reach a target cell ((g_x, g_y)) by moving one step at a time in the four cardinal directions (up, down, left, right). The creature can only move to cells that are empty. If the target cannot be reached, output (-1). The input consists of multiple test cases and terminates when a line with (0\ 0) is encountered. Your task is to compute and output the minimum number of steps required for each test case.

inputFormat

Standard input (stdin) consists of multiple test cases. Each test case begins with two integers (N) and (M) (the number of rows and columns). This is followed by (N) lines, each containing a string of (M) characters representing the grid. Next, there is a line with four integers: (s_x), (s_y), (g_x), (g_y), representing the starting and goal positions respectively. The input terminates with a line containing "0 0".

outputFormat

For each test case, output a single line containing the minimum number of steps required for the creature to reach the goal. If the goal is unreachable, print (-1).## sample

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

8