재미있는 파이프 퍼즐

시간 제한1초메모리 제한2048 MB

요약
2행 N열 격자에 놓인 파이프를 회전시켜 (1,1)에서 (2,N)까지 연결할 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
구현, 그래프, 시뮬레이션, 그리디
정답자
아직 제출이 없습니다

문제

진흥이는 재미있는 파이프 퍼즐을 풀고 있습니다. 이 퍼즐은 세로 22칸, 가로 NN칸 크기입니다. 위에서 ii번째이고 왼쪽에서 jj번째인 칸은 (i,j)(i, j)라고 표시합니다.

(1,1)(1, 1)과 (2,N)(2, N)을 제외한 각 칸에는 파이프가 하나씩 설치되어 있습니다. 파이프는 I자형 파이프와 L자형 파이프의 두 종류가 있습니다. 진흥이는 이 파이프들을 제자리에서 적절히 회전시켜 (1,1)(1, 1)에서 (2,N)(2, N)까지 파이프를 연결하려고 합니다.

그림 1. I자형 파이프는 회전시켜서 위의 두 모양을 만들 수 있습니다.

그림 2. L자형 파이프는 회전시켜서 위의 네 모양을 만들 수 있습니다.

각 칸마다 설치된 파이프의 종류가 주어질 때, 진흥이를 도와서 (1,1)(1, 1)에서 (2,N)(2, N)까지 파이프를 연결할 수 있는지 판단합시다.

그림 3. (1,1)(1, 1)에서 (2,N)(2, N)까지 파이프를 연결한 한 가지 경우입니다.

입력

첫 번째 줄에 퍼즐의 가로 칸 수 NN이 주어집니다.

두 번째 줄에 위쪽 칸들의 파이프 종류를 나타내는 길이 NN의 문자열이 주어집니다.

세 번째 줄에 아래쪽 칸들의 파이프 종류를 나타내는 길이 NN의 문자열이 주어집니다.

각 문자열에서 (1,1)(1, 1)과 (2,N)(2, N)에는 X가 대신 주어지며, I자형 파이프는 I로, L자형 파이프는 L로 주어집니다.

출력

파이프를 적절히 회전시켜 (1,1)(1, 1)에서 (2,N)(2, N)까지 파이프를 연결할 수 있으면 YES를, 불가능하면 NO를 출력합니다.

제한

  • 2≤N≤200,0002 \le N \le 200\\, 000

힌트

  • 예제 1: 그림 3에 해당하는 퍼즐입니다.
  • 예제 2: 파이프를 어떻게 돌려도 (1,1)(1, 1)에서 (2,4)(2, 4)까지 연결할 수 없습니다.

예제2

  1. 예제 1

    입력
    5
    XLLIL
    LILIX
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    4
    XLII
    LILX
    
    예상 출력
    NO