단어 찾기 퍼즐의 남은 글자

면접 대비

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

요약
글자 격자와 단어 목록이 주어질 때 8방향으로 모든 단어를 찾아 해당 글자를 지우고 남은 글자를 행 우선 순서로 출력합니다.
난이도

보통10점 중 4점

유형
행렬, 문자열 매칭, 완전 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

단어 찾기 퍼즐은 영어 소문자가 N행 N열로 놓인 표와, 표에서 찾아야 할 단어 목록으로 이루어진다.

퍼즐을 풀려면 목록의 각 단어가 표에 나타나는 모든 위치를 찾아야 한다. 단어는 어떤 칸에서든 시작할 수 있고, 위, 아래, 왼쪽, 오른쪽, 그리고 네 대각선 방향 중 하나로 일직선으로 놓일 수 있다. 단어가 한 번 발견될 때마다 그 단어를 이루는 모든 글자를 지운다.

모든 단어를 처리한 뒤, 지워지지 않은 글자를 행 우선 순서로 읽는다. 즉, 위쪽 행부터 아래쪽 행으로, 같은 행에서는 왼쪽에서 오른쪽으로 읽는다. 이렇게 얻은 문자열이 퍼즐의 정답이다.

주어진 퍼즐의 정답을 구하는 프로그램을 작성하라.

입력

첫째 줄에 표의 크기인 정수 N (1 <= N <= 10)이 주어진다.

다음 N개 줄에는 표의 한 행을 나타내는 영어 소문자 N개가 주어진다.

그다음 줄에 단어 목록에 있는 단어의 수 R (1 <= R <= 100)이 주어진다.

다음 R개 줄에는 목록의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 최대 10이다.

표의 모든 글자와 목록의 모든 단어는 영어 소문자 (a부터 z)로만 이루어져 있다.

출력

퍼즐의 정답을 한 줄에 출력한다.

입력은 지워지지 않고 남는 글자가 적어도 하나 존재하도록 주어진다.

예제3

  1. 예제 1

    입력
    2
    ab
    cd
    1
    ad
    
    예상 출력
    bc
    
  2. 예제 2

    입력
    5
    patka
    guska
    macka
    klopa
    krava
    4
    patka
    guska
    macka
    krava
    
    예상 출력
    klopa
    
  3. 예제 3

    입력
    4
    rast
    plso
    tajv
    pnez
    6
    rast
    alan
    nt
    past
    taj
    bonus
    
    예상 출력
    povez