Minimum Steps in a Warehouse Grid

You are given a grid representing a warehouse. The grid has M rows and N columns. Each cell in the grid is either an open space (denoted as '.') or an obstacle (denoted as '#'). You are also given a starting position and a destination position in the grid. Your task is to compute the minimum number of steps required to go from the start to the destination using moves that go one cell up, down, left, or right. If no valid path exists, output -1.

Formally, if the grid is represented as a matrix G where a cell G[i][j] is available if and only if G[i][j] \neq '#', and you start at (s_r, s_c) and want to reach (e_r, e_c), then you need to find the shortest path (using Manhattan moves) from the start to the destination. The problem can be modeled as a breadth-first search (BFS) on a grid.

The number of steps is defined as the number of moves taken. When the start and destination positions are the same, the answer is 0.

In mathematical notation, if d(u,v) represents the minimum steps between position u and v, then we are asked to compute: $$ d(s, e) = \min_{\text{valid paths}} \; \text{number of moves}, $$ with the condition that if no such path exists then $$ d(s, e) = -1. $$

inputFormat

The input is read from standard input and consists of the following lines:

• The first line contains two integers M and N (the number of rows and columns respectively).
• The next M lines each contain a string of length N representing a row of the grid.
• The last line contains four integers: start_row, start_col, end_row, and end_col.

All indices are 0-indexed.

outputFormat

Output a single integer to standard output. This integer is the minimum number of steps required to go from the start position to the destination. If there is no path, output -1.

5 5
.....
..#..
..#P.
P.#..
.....
1 0 3 4

8