Minimum Moves to Reach Target

In this problem, you are given a grid representing a maze. The grid is composed of characters where a '#' character indicates a wall and a '.' character indicates a free cell. You are also provided with a starting cell and a target cell. The robot can move in the four cardinal directions (up, down, left, right) and can only move to cells that are free. The goal is to determine the minimum number of moves required for the robot to reach the target cell from the starting cell. If the target cell is unreachable, output $-1$.

Formally, let $G$ be a grid with $H$ rows and $W$ columns. The starting cell is given by $(sy, sx)$ and the target cell by $(ty, tx)$. You need to compute the minimum number of moves where each move is one step in one of the four directions, such that the robot moves from its current cell to an adjacent cell with a '.' (free cell). If no such sequence exists, return $-1$.

inputFormat

The first line contains two integers $H$ and $W$ representing the number of rows and columns of the grid. The next $H$ lines each contain a string of length $W$, representing the grid where '#' is a wall and '.' is a free cell. The last line contains four integers: $sy$, $sx$, $ty$, and $tx$, which denote the row and column of the starting cell and the target cell respectively (0-indexed).

outputFormat

Output a single integer representing the minimum number of moves required for the robot to reach the target cell from the starting cell. If the target cannot be reached, output $-1$.## sample

4 4
####
#..#
#..#
####
1 1 2 2

2