After attending the lectures for all his normal courses, Max has to attend his List I Communication credit lecture.
To get to his lecture, he has to traverse through a hallway made of either students represented with an
S
or empty spaces represented with a .
.
He starts walking at (the top-left corner) and wants to get to his class at
(the bottom-right corner).
Max can move from one cell to another if both cells are empty space and share a corner or edge (i.e., he can move in all directions).
Since all the other students are walking to their List I Communication credit, they do not move, which enrages Max.
Because Max is enraged, he can remove at most students from the hallway.
Can Max travel from to
?
Constraints
and
will always be empty space.
Input Specification
The first line will contain an integer, , the number of columns in the hallway.
The next lines will contain
characters that are each either an
S
or .
, the hallway filled with students or empty space, respectively.
Output Specification
Output YES
if he can travel from to
by removing at most
students; otherwise, output
NO
.
Sample Input 1
6
.SS.SS
.SS.S.
Sample Output 1
NO
Explanation for Sample 1
Regardless of the students removed, Max cannot travel from
to
.
Sample Input 2
5
.S.S.
.S.S.
Sample Output 2
YES
Explanation for Sample 2
If the students at and
are removed, Max can travel from
to
.
Note that there are multiple valid solutions.
Comments
i remove u