단어 찾기

면접 대비

시간 제한1초메모리 제한256 MB

요약

여덟 방향으로 격자에서 단어들을 찾아 남은 글자를 모으고 없거나 겹치면 정해진 문구를 출력합니다.

난이도: 보통10점 중 5점
유형: 문자열 매칭, 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

격자에서 여덟 방향으로 단어를 찾는 퍼즐이다. 모든 단어가 존재하고 각 단어의 위치가 유일하면, 사용되지 않은 글자를 위에서 아래, 왼쪽에서 오른쪽 순으로 이어 solution을 출력한다. 단어가 없으면 no solution, 위치가 둘 이상이면 ambiguous, 남는 글자가 없으면 empty solution을 출력한다.

입력

첫 줄에 테스트 수가 주어진다. 각 테스트는 단어 수 $n$ , 높이 $h$ , 너비 $w$ , $h$ 줄의 격자, $n$ 개의 단어로 구성된다.

출력

각 테스트마다 solution 문자열 또는 no solution, ambiguous, empty solution 중 하나를 출력한다.

예제1

예제 1

입력

4
10 7 8
ELIPMOCN
TACODEOL
IMELBORP
MGOALRRM
BIPLEIEA
UCATZUCE
SBHEMSTT
BAPC
TUE
TEAM
PROBLEM
CODE
COMPILE
SUBMIT
CORRECT
BALLOON
PRIZE
2 4 3
BCB
AOA
PDP
CEC
BAPC
CODE
3 4 3
BCB
AOA
PDP
CEC
BAPC
CODE
TEAM
2 2 10
DELEVELEDB
ATESTSETPC
DELEVELED
TESTSET

예상 출력

ALGORITHMS
ambiguous
no solution
BAPC