Minimum Steps to Collect All Gold

You are given an (N \times N) grid representing a field. Each cell of the grid can contain one of the following characters: 'S' for the starting position, 'G' for a cell containing gold, 'R' for a rock (which is an impassable obstacle), and '.' for an empty cell. Your task is to determine the minimum number of steps required to collect all the gold by moving in the four cardinal directions (up, down, left, right). You must start at the cell marked 'S' and move sequentially from one gold cell to the next using a greedy strategy: at each step, choose the nearest reachable gold cell. If some gold is unreachable, print (-1).

The input is read from standard input and the output should be written to standard output.

inputFormat

The first line contains a single integer (N), the size of the grid. The following (N) lines each contain a string of length (N) representing a row of the grid. Each character in the string is one of 'S', 'G', 'R', or '.'.

outputFormat

Print a single integer representing the minimum number of steps required to collect all the gold, or (-1) if it is impossible.## sample

5
.RG..
.RG..
..SR.
.RRR.
..G..

10