거울 동굴
면접 대비시간 제한8초메모리 제한512 MB
두 사람이 W 곱하기 H 크기의 두 격자에서 거울 대칭으로 움직인다. 한 명이 벽에 막히면 그대로 있고, 두 사람이 동시에 각자의 목적지 칸에 도달할 수 있는지 판정한다.
문제
쌍둥이 모험가 Rin과 Len은 거울 동굴에서 보물을 찾고 있다. 이 동굴에는 거울의 방이라는 한 쌍의 방이 있고, 그 방의 문 너머에는 값비싼 보물이 잠들어 있다고 한다.
편의상 두 방은 각각 W × H개의 셀이 격자 모양으로 늘어선 것으로 본다. 방의 바깥쪽은 벽으로 둘러싸여 있다. 또한 방 안쪽에도 곳곳에 벽이 설치되어 있으며, 벽이 있는 셀에는 진입할 수 없다. 보물방의 문을 열려면 두 사람이 좌우대칭으로 움직여서 동시에 특정 셀에 도달해야 한다. 게다가 한쪽만 먼저 도달하면 문이 잠겨서 열리지 않게 된다.
좌우대칭의 움직임이란 북과 북, 서와 동, 동과 서, 남과 남으로 각각 동시에 움직이는 것을 의미한다. 다만 한쪽이 움직이려는 곳에 벽이 있고 다른 쪽이 움직이려는 곳에 벽이 없는 상황에서도 좌우대칭의 움직임으로 인정된다. 이 경우 벽이 있는 쪽은 제자리에 머물고, 벽이 없는 쪽은 옆 셀로 움직인다.
입력으로 쌍둥이의 초기 위치, 목적지, 장애물의 배치가 주어진다. 이 쌍둥이가 문을 열 수 있는지 판정하는 프로그램을 작성하라.
입력
입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
W H
RoomL1 RoomR1
RoomL2 RoomR2
...
RoomLH RoomRH
첫 줄에는 두 양의 정수 W, H (1 ≤ W, H ≤ 50)가 공백 하나로 구분되어 주어진다. 그다음 H줄에 걸쳐 두 방의 정보가 주어진다. RoomL**i, RoomR**i는 각각 왼쪽 방, 오른쪽 방의 i번째 행에 대응한다. 둘 다 길이 W의 문자열이며, j번째 문자가 방의 j번째 열에 대응한다. 각 문자는 다음 중 하나이다.
.: 자유롭게 이동할 수 있는 셀#: 벽이 있는 셀 (진입할 수 없다)%: 목적지R: Rin의 초기 위치L: Len의 초기 위치
각 방 모두 1번째 행이 방의 북쪽 끝, 1번째 열이 방의 서쪽 끝에 대응한다. 또한 각 방에는 목적지가 반드시 정확히 하나 있고, 왼쪽 방에는 Len, 오른쪽 방에는 Rin의 초기 위치가 정확히 하나 있다.
입력의 끝은 공백으로 구분된 두 개의 0을 포함하는 줄로 나타낸다.
출력
각 데이터 세트에 대해 쌍둥이가 문을 열 수 있으면 Yes, 열 수 없으면 No를 한 줄에 출력하라.