## Max's Anger Contest Series 1 P2 - Wesley's Anger Contest 7 P1 - Enraged

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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.