우사인은 3D 프린터로 만든 3D 퍼즐을 파는 온라인 상점을 운영합니다. 최근 가장 많이 풀리는 퍼즐은 나사 미로입니다. 해당 퍼즐은 미로가 양각된 나사 모양 부품과 너트 부품 두 개로 나누어져 있습니다. 너트의 안쪽에 돌출부가 있을 수 있습니다. 해당 돌출부 때문에 너트는 미로의 길을 따라서만 미끄러지며 움직일 수 있습니다.
초기 두 부품은 분리되어 있습니다. 목표는 너트를 움직여 미로를 통과해 너트가 볼트 머리에 닿게 하는 것입니다. 너트는 시계 방향, 반시계 방향, (나사 머리 방향인) 아래, (나사 머리에서 멀어지는 방향인) 위로 움직일 수 있습니다. 모든 움직임은 너트 안쪽의 모든 돌출부가 미로 벽에 의해 새 위치로 가는 것이 막히지 않을 때만 가능합니다. 이미 언급된 움직임 외로 가능한 것이 하나 더 있습니다: 볼트와 너트가 분리되어 있을 때, 너트를 뒤집을 수 있습니다. 아래의 그림은 퍼즐의 두 가지 부품 및 가능한 움직임을 나타냅니다.
(그림 참조)
어떤 소비자가 많은 양의 나사 미로를 주문했습니다. 우사인이 무작위로 서로 다른 모양의 퍼즐을 디자인했지만, 마감 일자가 촉박하고 주문이 워낙 많아 우사인은 퍼즐을 풀 방법이 있는지 없는지 검증할 수 없습니다. 우사인은 너트와 볼트가 주어질 때 결과를 빠르게 찾는 알고리즘을 고안할 것을 당신에게 부탁했습니다. 이를 위해 너트의 안쪽 부분은 원형 이진 문자열로 주어집니다. 볼트에 있는 미로의 각 행도 마찬가지입니다.
입력
첫 줄에 정수 R (1 <= R <= 1000)과 C (3 <= C <= 100)가 주어지는데, 각각 미로의 행과 열의 개수를 의미합니다. 둘째 줄에는 길이 C의 원형 이진 문자열 S가 주어지는데, 너트의 안쪽을 나타냅니다. S의 각 문자는 너트의 해당 부분이 돌출부일 경우 "1", 빈 공간일 경우 "0"으로 주어집니다. 다음 R개 줄에 미로의 행을 나타내는 원형 문자열이 주어집니다. 이때, 문자열에서 문자는 미로의 해당 부분이 벽일 경우 "1", 빈 공간일 경우 "0"으로 주어집니다. 행은 (볼트의 끝인) 위에서 (볼트의 머리인) 아래 방향으로 주어집니다.
출력
하나의 줄에 만약 퍼즐을 풀 방법이 있다면 대문자 "Y"를, 그렇지 않다면 대문자 "N"를 출력합니다.
힌트 (역자 : 예제 아래에 있습니다.)
아래 그림은 첫 번째 예시를 나타냅니다. 왼쪽 그림은 퍼즐 해결 각 단계에서 3D 시야를 나타냅니다. 가운데 그림은 해당하는 3D 시야를 2D로 만든 것입니다. 마지막으로, 오른쪽 그림은 제시된 입력에서 퍼즐 해결 각 단계의 상태를 나타냅니다 (이해를 돕기 위해 "1"은 기호로, "0"은 빈 공간으로 대체했습니다).
위 세 그림은 (세 개의 돌출부가 있는) 너트와 볼트가 분리된 채 시작하는 모습입니다. 2번째 세 그림은 너트가 (볼트 머리 방향으로) 네 행 내려간 후 상태를 나타냅니다. 이후 너트가 한 번 돌고, 아래로 두 행 가고, 반대 방향으로 네 번 돌고, 마지막으로 세 행 내려가면 퍼즐이 풀립니다. 해당 상황에서 너트는 뒤집히지도 않고 (볼트 머리 반대 방향으로) 올라가지도 않았음에 유의합시다.
ez_code 8달 전 1
문제
우사인은 3D 프린터로 만든 3D 퍼즐을 파는 온라인 상점을 운영합니다. 최근 가장 많이 풀리는 퍼즐은 나사 미로입니다. 해당 퍼즐은 미로가 양각된 나사 모양 부품과 너트 부품 두 개로 나누어져 있습니다. 너트의 안쪽에 돌출부가 있을 수 있습니다. 해당 돌출부 때문에 너트는 미로의 길을 따라서만 미끄러지며 움직일 수 있습니다.
초기 두 부품은 분리되어 있습니다. 목표는 너트를 움직여 미로를 통과해 너트가 볼트 머리에 닿게 하는 것입니다. 너트는 시계 방향, 반시계 방향, (나사 머리 방향인) 아래, (나사 머리에서 멀어지는 방향인) 위로 움직일 수 있습니다. 모든 움직임은 너트 안쪽의 모든 돌출부가 미로 벽에 의해 새 위치로 가는 것이 막히지 않을 때만 가능합니다. 이미 언급된 움직임 외로 가능한 것이 하나 더 있습니다: 볼트와 너트가 분리되어 있을 때, 너트를 뒤집을 수 있습니다. 아래의 그림은 퍼즐의 두 가지 부품 및 가능한 움직임을 나타냅니다.
(그림 참조)
어떤 소비자가 많은 양의 나사 미로를 주문했습니다. 우사인이 무작위로 서로 다른 모양의 퍼즐을 디자인했지만, 마감 일자가 촉박하고 주문이 워낙 많아 우사인은 퍼즐을 풀 방법이 있는지 없는지 검증할 수 없습니다. 우사인은 너트와 볼트가 주어질 때 결과를 빠르게 찾는 알고리즘을 고안할 것을 당신에게 부탁했습니다. 이를 위해 너트의 안쪽 부분은 원형 이진 문자열로 주어집니다. 볼트에 있는 미로의 각 행도 마찬가지입니다.
입력
첫 줄에 정수 R (1 <= R <= 1000)과 C (3 <= C <= 100)가 주어지는데, 각각 미로의 행과 열의 개수를 의미합니다. 둘째 줄에는 길이 C의 원형 이진 문자열 S가 주어지는데, 너트의 안쪽을 나타냅니다. S의 각 문자는 너트의 해당 부분이 돌출부일 경우 "1", 빈 공간일 경우 "0"으로 주어집니다. 다음 R개 줄에 미로의 행을 나타내는 원형 문자열이 주어집니다. 이때, 문자열에서 문자는 미로의 해당 부분이 벽일 경우 "1", 빈 공간일 경우 "0"으로 주어집니다. 행은 (볼트의 끝인) 위에서 (볼트의 머리인) 아래 방향으로 주어집니다.
출력
하나의 줄에 만약 퍼즐을 풀 방법이 있다면 대문자 "Y"를, 그렇지 않다면 대문자 "N"를 출력합니다.
힌트 (역자 : 예제 아래에 있습니다.)
아래 그림은 첫 번째 예시를 나타냅니다. 왼쪽 그림은 퍼즐 해결 각 단계에서 3D 시야를 나타냅니다. 가운데 그림은 해당하는 3D 시야를 2D로 만든 것입니다. 마지막으로, 오른쪽 그림은 제시된 입력에서 퍼즐 해결 각 단계의 상태를 나타냅니다 (이해를 돕기 위해 "1"은 기호로, "0"은 빈 공간으로 대체했습니다).
위 세 그림은 (세 개의 돌출부가 있는) 너트와 볼트가 분리된 채 시작하는 모습입니다. 2번째 세 그림은 너트가 (볼트 머리 방향으로) 네 행 내려간 후 상태를 나타냅니다. 이후 너트가 한 번 돌고, 아래로 두 행 가고, 반대 방향으로 네 번 돌고, 마지막으로 세 행 내려가면 퍼즐이 풀립니다. 해당 상황에서 너트는 뒤집히지도 않고 (볼트 머리 반대 방향으로) 올라가지도 않았음에 유의합시다.