십자말풀이
면접 대비시간 제한1초메모리 제한1024 MB
세 단어를 교차시켜 모두 연결된 낱말 퍼즐을 만들고, 교차하는 글자의 위치를 출력합니다.
문제
브리기타는 어린 남동생을 위해 십자말풀이를 만들려고 한다. 너무 어렵지 않도록 십자말풀이는 세 단어로만 구성된다. 올바른 십자말풀이는 다음 규칙을 만족한다:
- 단어는 가로(수평) 또는 세로(수직)로 쓴다.
- 두 단어가 교차(겹침)하면, 정확히 한 글자에서 만난다.
- 모든 단어는 최소 하나의 다른 단어와 교차한다. 즉, 세 단어가 모두 서로 연결되어 있다.
- 한 단어가 다른 두 단어와 교차하면, 두 교차점은 서로 다른 위치여야 한다. 예를 들어 KURMIS 단어는 KAVA, KELMAS 단어와 K 글자에서 교차할 수 없다.
주어진 세 단어로 십자말풀이를 만들어라. 가능한 해가 여러 개면 그중 아무거나 출력한다.
입력
세 줄에 각각 대문자 라틴 문자로 이루어진 단어가 하나씩 주어진다. 주어진 단어로는 규칙을 만족하는 십자말풀이를 항상 만들 수 있다.
출력
서로 교차하는 단어 쌍과 교차하는 글자의 번호를 한 줄에 한 쌍씩 출력한다. 첫 번째 단어, 그 단어가 두 번째 단어와 교차하는 글자의 번호, 이어서 두 번째 단어, 그 단어가 첫 번째 단어와 교차하는 글자의 번호 순으로 출력한다. 예를 들어 VANDUO와 PIENAS가 A 글자에서 교차하면 VANDUO 2 PIENAS 5를 출력한다.