순환 단어 찾기
시간 제한1초메모리 제한1024 MB
가장자리에서 이어지는 격자에서 각 단어의 시작 위치와 방향(R, D, L, U)을 찾습니다.
문제
단어 찾기 퍼즐은 글자로 이루어진 격자에서 지정된 단어를 찾는 문제이다. 단어는 격자의 행, 열, 또는 대각선을 따라 연속된 글자로 놓여 있다. 더 어려운 단어 찾기에서는 이 방향들 중 어느 방향으로든 단어를 정방향이나 역방향으로 읽을 수 있다. '순환 단어 찾기'에서는 단어가 격자의 가장자리를 넘어 반대편에서 같은 줄을 따라 이어질 수 있고, 같은 단어의 글자를 다시 사용할 수도 있다. 이 문제에서는 대각선을 따라 찾지 않고 행과 열만 검색한다. (UCF 프로그래밍 코치들은 정말 친절하다!)
글자 격자와 단어 목록이 주어지면, 각 단어의 첫 글자 위치와 그 단어의 나머지 글자가 순서대로 이어지는 방향을 찾아라.
입력
첫 줄에는 단어 찾기 퍼즐의 개수를 나타내는 양의 정수 n이 주어진다. 이어서 각 퍼즐의 데이터가 주어진다. 각 퍼즐의 첫 줄에는 공백으로 구분된 두 양의 정수 r과 c가 주어진다. r은 격자의 행 수로 3 이상 12 이하이고, c는 열 수로 3 이상 20 이하이다. 다음 r줄에는 공백 없이 정확히 c개의 대문자 알파벳이 주어진다. 그다음 줄에는 찾을 단어의 개수를 나타내는 양의 정수 s가 주어진다. 이어서 s줄에 찾을 단어가 한 줄에 하나씩 주어진다. 단어는 대문자 알파벳으로만 이루어지며, 길이는 3 이상 100 이하이다. 단어가 어떤 언어에서든 실제 단어일 필요는 없다.
각 단어는 격자에 정확히 한 번 나타나며, 시작 위치는 하나이고 한 방향으로만 놓여 있다. 어떤 단어도 회문이 아니다. 입력은 여기에 설명된 대로 올바르다고 가정한다.
출력
각 단어 찾기 퍼즐마다 'Word search puzzle #p:' 줄을 출력한다. 여기서 p는 입력에서의 퍼즐 번호이며 1부터 센다. 그다음 해당 퍼즐에 주어진 단어를 주어진 순서대로 하나씩 'd r c w' 형식의 줄로 출력한다. w는 단어이고, r은 단어의 첫 글자가 있는 행 번호(1부터 센다), c는 첫 글자가 있는 열 번호(1부터 센다)이다. d는 첫 글자를 기준으로 나머지 글자가 놓인 방향이며, 아래 한 글자 코드를 사용한다. d, r, c 각각의 뒤에는 공백을 정확히 하나씩 출력한다.
각 퍼즐의 출력 뒤에는 빈 줄을 하나 남긴다.