Shortest Path in a Grid

This problem requires you to determine the shortest path from the top-left cell to the bottom-right cell in an \(N \times M\) grid. The grid is composed of cells that are either open ('O') or blocked ('X'). You can move up, down, left, or right, but you cannot pass through a blocked cell.

Specifically, you are given:

• An integer \(N\) and \(M\), the number of rows and columns of the grid respectively.
• An \(N \times M\) grid where each cell is either 'O' (open) or 'X' (blocked).

Your task is to compute the minimum number of moves required to go from cell \((0,0)\) to cell \((N-1,M-1)\). Moves are allowed only in the four cardinal directions: up, down, left, and right.

Note:

• If the starting cell \((0,0)\) or the destination cell \((N-1,M-1)\) is blocked, then the answer is \(-1\).
• If no valid path exists from the start to the destination, output \(-1\).
• If the grid is of size \(1 \times 1\) and the cell is open, the path length is \(0\).

The solution typically involves a Breadth-First Search (BFS) algorithm. In BFS, the grid is treated as a graph where each cell is a node and moves to adjacent open cells are edges connecting the nodes. The shortest path is found by exploring the grid level by level.

inputFormat

The first line contains two integers, \(N\) and \(M\), representing the number of rows and columns in the grid.

The next \(N\) lines each contain \(M\) characters separated by spaces. Each character is either 'O' (open) or 'X' (blocked).

outputFormat

Output a single integer representing the minimum number of moves required to travel from the top-left corner to the bottom-right corner. If such a path does not exist, output \(-1\).

## sample

4 4
O O X O
O X O O
O O O X
O X O O

6