Minimum Moves to Target in a Minefield

You are given an M x N grid representing a minefield, where each cell is either safe (denoted by 0) or contains a mine (denoted by 1). You are also provided with a starting cell and a target cell. Your task is to compute the minimum number of moves required to reach the target cell from the starting cell without stepping on any mines. Moves can only be made in the four cardinal directions: up, down, left, and right.

If either the starting cell or the target cell contains a mine, or if there is no valid path, your program should output -1.

The movement cost is defined as follows:

\( \text{moves} = \lvert r_t - r_s \rvert + \lvert c_t - c_s \rvert\) in the best-case scenario (when there are no obstacles), but obstacles (mines) may force a longer route.

inputFormat

The input is provided via standard input (stdin) and has the following format:

M N
row_1
row_2
... 
row_M
r_s c_s r_t c_t

where:

• M and N are the number of rows and columns of the grid respectively.
• Each row_i consists of N space-separated integers (either 0 or 1), representing the grid cells.
• r_s and c_s denote the row and column indices of the starting cell (0-indexed).
• r_t and c_t denote the row and column indices of the target cell (0-indexed).

outputFormat

The output should be printed to standard output (stdout) and consist of a single integer which is the minimum number of moves required to move from the starting cell to the target cell without stepping on any mines. If such a move is impossible, output -1 instead.

## sample

5 5
0 0 1 0 0
0 1 0 1 0
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
0 0 4 4

8