Minimum Moves in Grid

You are given a grid with N rows and M columns. Each cell of the grid is either open, denoted by 'O', or blocked, denoted by 'X'. The task is to determine the minimum number of moves required to go from a starting position \((S_x, S_y)\) to a target position \((T_x, T_y)\) by moving one cell at a time in the four cardinal directions (up, down, left, right). If the target cannot be reached, output -1.

Note: The positions are zero-indexed. A move consists of stepping into an adjacent open cell. The lower bound on the number of moves is given by the Manhattan distance: \(|S_x - T_x| + |S_y - T_y|\), though obstacles may force a longer path or make it unreachable.

inputFormat

The input is given from standard input and has the following format:

N M
row_1
row_2
...
row_N
Sx Sy Tx Ty

Where:

• N and M are the number of rows and columns in the grid.
• Each row_i is a string of length M consisting of the characters 'O' and 'X'.
• Sx Sy represent the starting position and Tx Ty represent the target position (0-indexed).

outputFormat

Output a single integer, which is the minimum number of moves required to reach the target from the start. If it is impossible to reach the target, output -1.

5 5
OOOXO
OXOXO
OXOOO
OXXXO
OOOOO
0 0 4 4

8