Description
N x N 크기의 문자 행렬에서 특정 단어를 찾는 프로그램을 작성하시오.
이 행렬은 대문자로만 구성되어 있으며, 행렬의 가로(왼쪽에서 오른쪽) 또는 세로(위에서 아래) 방향에서 주어진 단어를 찾아야 한다. 단어를 찾을 때는 가로 또는 세로 방향만 고려하며. 대각선 방향은 고려하지 않는다.
Input
첫 번째 줄에는 테스트케이스의 수 T가 입력된다(1 <= T <= 20).
그 다음줄 부터 T 세트만큼 아래 형식의 입력이 주어진다.
행렬의 크기를 나타내는 정수 N이 입력된다(1 ≤ N ≤ 50).
다음 N개의 줄에 걸쳐 각각 N개의 대문자가 주어진다(각 줄의 문자들은 공백 없이 연속해서 주어진다.)
그 다음 줄에 찾아야 할 단어가 주어진다. 이 단어는 대문자로만 구성되며, 길이는 최대 50이다.
Output
각 테스트케이스별로 한 줄에 하나씩 행렬 내에서 주어진 단어를 찾을 수 있다면 YES, 그렇지 않다면 NO를 출력한다.
2
5
ABCGE
BCDOF
CDAOG
DEDDH
EFGHI
GOOD
8
ABCDEABC
BCDEFBCD
CDEFGCDE
DEFGHDEF
ABCDEABC
EFGHIEFG
BCDEFBCD
ABCDEABC
GREAT