Shortest Path in a Garden Grid

You are given a grid representing a garden. Each cell is either open (O) or blocked (X). Your task is to find the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1,m-1)) of the grid. You can only move in four directions: up, down, left, or right.

If either the starting or the destination cell is blocked, or if no path exists between these two cells, output -1.

The number of steps is defined as the number of moves between adjacent cells. Note that if the grid is only 1x1 and the cell is open, the minimum steps is 0 because you are already at the destination.

The problem can be formally stated as follows. Given an n×m grid, let \(\text{grid}_{i,j}\) denote the value at row \(i\) and column \(j\). You are to compute the minimum number of steps required to get from \( (0,0) \) to \( (n-1,m-1) \) using moves defined by:

[ (x,y) \rightarrow (x+1,y), \quad (x,y) \rightarrow (x-1,y), \quad (x,y) \rightarrow (x,y+1), \quad (x,y) \rightarrow (x,y-1). ]

If the path does not exist, return \(-1\).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000), representing the number of rows and columns of the grid respectively.

The following n lines each contain a string of length m consisting of the characters O (open cell) and X (blocked cell). These represent the grid.

outputFormat

Output a single integer representing the minimum number of steps required to travel from the top-left corner to the bottom-right corner. If it is not possible, output -1.

## sample

5 5
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

8