Indian National Olympiad in Informatics

Related:

Online Programming Contest, 8-9 October 2005

IARCS home > OLYMPIAD

Basic Division

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