BOJ 25897 Loopy Word Search

문제 링크:

문제 내용

단어 찾기 퍼즐을 푸는 프로그램을 작성하세요. 이 문제에서는 단어가 가로와 세로로만 나타납니다. 대신 맨 오른쪽 세로줄에 있는 칸에서 오른쪽으로 더 가면 맨 왼쪽 세로줄의 같은 가로줄의 칸으로 이어지며, 맨 위와 맨 아래 가로줄도 마찬가지입니다. 예시 그림을 참고하세요. 단어가 길면 같은 칸을 여러 번 거칠 수도 있습니다.

입력

첫 줄에는 테스트 케이스의 개수가 주어집니다.

각각의 테스트 케이스에 대해, 첫 줄에는 퍼즐의 가로줄의 수 $r$과 세로줄의 수 $c$가 주어지며, 다음 $r$줄에는 단어를 찾아야 하는 퍼즐 판이 주어집니다. ($3 \le r \le 12$, $3 \le c \le 20$) 퍼즐 판은 알파벳 대문자로만 이루어져 있습니다.

그다음 줄에는 찾아야 하는 단어의 개수 $n$이 주어지며, 다음 $n$줄에는 단어가 한 줄에 하나씩 공백 없이 주어집니다. 각 단어의 길이는 3 이상 100 이하이며, 주어진 퍼즐 내에서 단어의 위치는 유일함이 보장됩니다.

출력

각각의 테스트 케이스에 대해, 첫 줄에는 Word search puzzle #1:과 같이 출력하고, 그 다음 줄부터 각 단어에 대해 방향(LRUD), 가로줄 번호, 세로줄 번호, 단어 순으로 한 줄에 하나씩 출력합니다. 두 테스트 케이스 사이에는 빈 줄을 하나 출력합니다. 예제 출력을 참고하세요.

문제 풀이