Treasure Hunt: Minimum Steps to Treasure

You are given a grid with n rows and m columns. Each cell in the grid is either open (denoted by 'O') or blocked (denoted by 'R'). Starting from the top-left cell (0-indexed) at position (0, 0), your task is to find the minimum number of steps required to reach the treasure located at the bottom-right cell (n-1, m-1). You can move in four directions: up, down, left, and right. If the starting or ending cell is blocked, or if there is no possible path, output -1.

The problem can be mathematically formulated as follows: Let \(S(x, y)\) be the minimum steps to reach cell \((x, y)\). Then:

[ S(x, y) = \min_{(dx,dy) \in {(1,0), (-1,0), (0,1), (0,-1)}} { S(x+dx, y+dy) } + 1 ]

Note: The above recurrence holds for movements within valid, unblocked cells.

inputFormat

The first line contains two integers n and m separated by a space, indicating the number of rows and columns respectively. The following n lines each contain a string of length m representing a row of the grid. Each character is either 'O' (open) or 'R' (blocked).

outputFormat

Output a single integer representing the minimum number of steps required to reach the treasure from the top-left corner. If no valid path exists, output -1.

4 4
OOOO
ORRO
OOOO
RROO

6