Problem 1: Ant Paths, *(K Narayan Kumar, CMI)*

Goody the ant is crawling over a rectangular grid consisting of
*M ×N* cells. Each cell in the grid is marked with one of
{`.`,`L`,`R`,`S`}. Goody can move from a
cell to any one of its four neighbours subject to the following
conditions: From a cell marked with a "`.`", Goody can move in
any direction. From a cell marked with an "`L`" he must move
left with respect to the direction he was moving when he entered this
cell. From a cell marked with an "`R`", he must move right
with respect to the direction he was moving when he entered this
cell. If a cell is marked "`S`" his crawl comes to a stop. You
may assume that all the cells on the boundary are marked with
"`.`", so that it is always possible to move following the
rules.

Given a description of the grid and the cell where Goody begins
his crawl (you may assume that this cell is always marked with a
"`.`") your task is to determine the minimum number of steps
that Goody needs to take before he reaches a cell marked with
"`S`".

For example, here is a 7 ×8 grid. Goody starts at the cell
(4,1) - that is, the cell in row 4, column 1. He can reach the
"`S`" labelled cell at (2,4) by following the sequence (4,1),
(3,1), (2,1), (1,1), (1,2), (1,3), (1,4), (2,4) and this takes 7
steps. He can also reach that cell in 5 steps by using the following
shorter sequence: (4,1), (4,2), (4,3), (3,3), (2,3), (2,4). You can
check that this is indeed the shortest such sequence to any cell
labelled with a `S`.

. . . . . . . . . L R S . L . . . . . . . . L . G . L . . R . . . . R . R . . . . . . . . . S . . . . . . . . .

Input format

The first line of the input consists of two integers *M*
and *N* indicating the number of rows and coloumns in the
grid. The next *M* lines contain *N* characters, each of
which is `.` or `L` or `R` or `S` or
`G`. There is exactly one cell in the grid marked with a
`G` and this is the cell from with Goody begins crawling.

Output format

If Goody can crawl to a cell labelled `S`, print a single
integer indicating the minimum number of steps required to reach
*some* cell labelled with `S`. Otherwise print -1.

Test data

You may assume that *N* ≤ 60 and *M* ≤ 60 in 80%
of the inputs. In all the inputs *N* ≤ 1000 and *M*
≤ 1000.

Example

We now illustrate input and output formats using the example described above.

Sample input

7 8 ........ .LRS.L.. ......L. G.L..R.. ..R.R... ......S. ........

Sample output

5

Copyright (c) IARCS 2003-2020; Last Updated: 10 Jan 2006