15705번 - 단어 찾기

N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다. 단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오.

단어 S가 표에 존재하려면, 표의 한 칸에서 시작해, 연속해서 그 단어의 모든 알파벳이 순서대로 등장해야 한다. 이때, 연속하는 방향은 위, 아래, 오른쪽, 왼쪽, 대각선 방향 모두 가능하다. 대각선 방향은 왼쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 아래 방향이 모두 가능하다. 연속하는 방향이 중간에 바뀌면 안 된다.

첫째 줄에 길이가 100보다 작거나 같은 단어 S가 주어진다. S는 알파벳 대문자로만 이루어져 있다.

둘째 줄에는 표의 행의 개수 N과 열의 개수 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이다.

셋째 줄부터 N개의 줄에는 표의 각 행에 들어있는 알파벳이 주어진다.

입력으로 주어진 표에 단어 S가 존재하면 1을, 없으면 0을 출력한다.

예제 1의 경우에 ABCD는 아래와 같이 등장한다.

ACDBE
ABCED
ACCEE
ACHDF
ACBCE

예제 2의 경우에 STR은 등장한다. STR은 매우 많이 등장하는데, 일부를 아래에 굵게 표시했다.

STARTS
STRSTR
RRTSRE
SRSTRR
STRTSR
STSTSS