Path Existence in a Grid

You are given a square grid of characters. Each cell in the grid contains one of the following symbols:

• S representing the starting point,
• E representing the ending point,
• . representing an open cell,
• # representing a wall which cannot be traversed.

Your task is to determine whether there exists a valid path from S to E moving only in the four cardinal directions (up, down, left, right). The path can only move through cells marked as . or the destination E. If either the start or end point is missing, the answer is false.

The underlying algorithm is Breadth-First Search (BFS). One can formally describe the condition for a valid move by the equation:

\( 0 \leq i < n, \quad 0 \leq j < n \quad \text{and} \quad grid[i][j] \in \{'.', 'E'\} \).

Implement your solution so that it reads input from standard input and writes the result to standard output.

inputFormat

The input is given via standard input. The first line contains an integer n denoting the size of the grid (number of rows; the grid is square). The next n lines each contain a string of length n representing a row of the grid. Each character is one of S, E, . or #.

outputFormat

Print true if there exists a valid path from S to E, and false otherwise. The output should be written to standard output.

4
S...
.##.
..#E
....

true