Maze Path Finder

You are given a square maze of size \(n \times n\), represented as an \(n\)-by-\(n\) grid. Each cell in the maze contains either 'S' (indicating a safe, passable cell) or '*' (indicating a blocked cell). Additionally, you are provided with a starting coordinate \((s_x, s_y)\) and an ending coordinate \((e_x, e_y)\) (both 0-indexed).

Your task is to determine whether there exists a valid path from the start cell to the end cell. You may move in the four cardinal directions: up, down, left, and right. Note that you cannot move diagonally, leave the maze boundaries, or step onto a blocked cell. If the start and end positions are identical, the answer is considered True.

Input and Output specifications: The program should read from standard input (stdin) and print to standard output (stdout).

inputFormat

The input format is as follows:

1. The first line contains an integer \(n\), representing the size of the maze.
2. The next \(n\) lines each contain \(n\) characters separated by a single space representing the maze. Each character is either S or *.
3. The following line contains two integers \(s_x\) and \(s_y\), the starting cell coordinates.
4. The last line contains two integers \(e_x\) and \(e_y\), the ending cell coordinates.

outputFormat

Output a single line containing either True if there is a valid path between the start and the end cell, or False otherwise.

4
S S S *
* * S S
S S * S
S * S S
0 0
3 3

True