Grid Navigation

You are given a grid consisting of characters 'G' and 'R', where 'G' represents grass and 'R' represents rock. You start at the top-left cell (i.e. at position \( (0,0) \)) and your goal is to reach the bottom-right cell (i.e. at position \( (n-1, m-1) \)). You can only move one step at a time in the four cardinal directions: up, down, left, and right. You may only step on cells that contain grass ('G').

Determine whether there exists a path from the start to the goal. If such a path exists, output True; otherwise, output False.

inputFormat

The first line contains a single integer \( n \) representing the number of rows in the grid. Each of the next \( n \) lines contains a non-empty string of equal length consisting only of the characters 'G' and 'R', representing a row of the grid.

You may assume that \( 1 \leq n \leq 10^3 \) and the length of each row is between 1 and \( 10^3 \). The grid is guaranteed to be rectangular.

outputFormat

Print a single line containing either True if a valid path exists from the top-left to the bottom-right cell, or False otherwise.

3
GGG
GRG
GGG

True