Minimum Steps in a Maze

You are given a maze represented by a grid with ( n ) rows and ( m ) columns. Each cell in the maze is either open ('.') or blocked ('#'). You are also given a starting position ( (x_{start}, y_{start}) ) and a target position ( (x_{target}, y_{target}) ). Your task is to compute the minimum number of steps required to move from the starting position to the target position by moving one cell at a time in the four cardinal directions (up, down, left, right). If the target is unreachable, output -1.

The Manhattan distance between two points ( (x_1,y_1) ) and ( (x_2,y_2) ) is given by ( |x_2-x_1| + |y_2-y_1| ), which is a lower bound on the number of steps required if there were no obstacles.

inputFormat

Input is read from standard input. The first line contains two integers ( n ) and ( m ) (the number of rows and columns, respectively). Each of the next ( n ) lines contains a string of length ( m ) that represents a row of the maze ('.' for open cells and '#' for obstacles). The last line contains four integers: ( x_{start}, y_{start}, x_{target}, y_{target} ), representing the starting and target positions. All positions are 0-indexed.

outputFormat

Output a single integer to standard output: the minimum number of steps required to reach the target. If the target is not reachable, output -1.## sample

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

8