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

View as PDF

Submit solution


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 2 \times N hallway made of either students represented with an S or empty spaces represented with a ..

He starts walking at (1, 1) (the top-left corner) and wants to get to his class at (2, N) (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 8 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 2 students from the hallway.

Can Max travel from (1, 1) to (2, N)?

Constraints

1 \le N \le 2 \times 10^5

(1, 1) and (2, N) will always be empty space.

Input Specification

The first line will contain an integer, N, the number of columns in the hallway.

The next 2 lines will contain N 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 (1, 1) to (2, N) by removing at most 2 students; otherwise, output NO.

Sample Input 1

6
.SS.SS
.SS.S.

Sample Output 1

NO

Explanation for Sample 1

Regardless of the 2 students removed, Max cannot travel from (1, 1) to (2, N).

Sample Input 2

5
.S.S.
.S.S.

Sample Output 2

YES

Explanation for Sample 2

If the students at (1, 2) and (1, 4) are removed, Max can travel from (1, 1) to (2, N).

Note that there are multiple valid solutions.


Comments


  • 0
    BaichenLuo  commented on Jan. 14, 2023, 4:05 p.m.

    i remove u