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×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

1N2×105

(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

Copy
6
.SS.SS
.SS.S.

Sample Output 1

Copy
NO

Explanation for Sample 1

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

Sample Input 2

Copy
5
.S.S.
.S.S.

Sample Output 2

Copy
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