Shortest Path in a Warehouse

A robot is tasked with navigating through a warehouse. The warehouse is represented as a grid with \(R\) rows and \(C\) columns. Each cell in the grid is either an open space, denoted by 'O', or a shelf, denoted by 'S'. The robot starts at the top-left corner (cell \((0,0)\)) and must reach the bottom-right corner (cell \((R-1, C-1)\)). It can move in four directions: up, down, left, or right, but it cannot move diagonally or pass through cells containing shelves.

Your task is to compute the length of the shortest path from the start to the destination. The length of the path is the number of moves between adjacent cells. If there is no valid path, output \(-1\).

inputFormat

Read from the standard input. The first line contains two space-separated integers \(R\) and \(C\), representing the number of rows and columns. The following \(R\) lines each contain a string of length \(C\), where each character is either 'O' (open space) or 'S' (shelf), representing the warehouse grid.

outputFormat

Print a single integer to the standard output — the length of the shortest path from the top-left corner to the bottom-right corner. If no valid path exists, print \(-1\).

5 5
OOOOO
OSSSO
OOOOO
OSSSO
OOOOO

8