단어 퍼즐
면접 대비시간 제한1초메모리 제한128 MB
글자 격자와 단어 목록이 주어질 때, 각 단어가 시작하는 칸과 8방향 중 읽는 방향을 찾고 행, 열, 방향 순으로 가장 앞선 위치를 출력한다.
문제
직사각형 격자판에서 여러 개의 단어를 찾는 단어 퍼즐을 푼다.
각 단어는 격자판 안에서 상하, 좌우, 대각선을 포함한 8개 방향 중 하나로 연속된 칸에 나타난다. 각 단어에 대해 단어가 시작하는 칸의 위치와, 그 칸에서부터 단어를 읽어 나가는 방향을 구하라.
가장 왼쪽 위 칸의 좌표는 이며, 아래로 갈수록 행 번호가, 오른쪽으로 갈수록 열 번호가 커진다.
방향은 북쪽을 A로 하여 시계 방향으로 A부터 H까지 붙인다.
입력
첫째 줄에 격자판의 행 수 , 열 수 , 찾아야 할 단어의 개수 가 주어진다 ().
다음 개의 줄에 격자판이 주어지며, 각 줄은 개의 대문자 알파벳으로 이루어진다.
이어서 개의 줄에 찾아야 할 단어가 한 줄에 하나씩 주어진다. 각 단어는 대문자 알파벳으로 이루어지며, 반드시 격자판 안에 존재한다.
출력
개의 줄에 걸쳐 각 단어의 답을 출력한다. 각 줄에는 단어가 시작하는 칸의 행 번호와 열 번호, 그리고 읽는 방향을 나타내는 문자(A~H)를 공백으로 구분하여 출력한다.
한 단어가 여러 위치에서 나타날 수 있다. 이때 다음 기준을 순서대로 적용하여 가장 앞서는 위치 하나만 출력한다.
- 행 번호가 더 작은 것
- 행 번호가 같으면 열 번호가 더 작은 것
- 행과 열 번호가 모두 같으면 방향 문자가 더 작은 것 (A가 가장 작고 H가 가장 크다)