13502번 - 단어퍼즐 2

문제

5 x 5 행렬에 대문자 알파벳이 하나씩 들어간 퍼즐이 있다. 그리고 이 행렬에서 주어진 단어들을 찾는 것이다. 찾는 방법은 임의의 시작점에서 시작하여 인접한 8방향으로 뻗어나가면서 알파벳을 이어나가는 것이다. 이때 같은 칸을 두 번 이상 방문할 수 없다. 찾을 단어들은 문제와 함께 배포된 dict.txt에 들어있는 단어들이다.

Z C C D X
K Q M N B
U O W Z Y
F C O I J
P A Q Z T

위와 같은 퍼즐이 있을 때 CAP, COW, COOK 등은 퍼즐에서 찾을 수 있지만 COD, PACK 등은 찾을 수 없다.

문제는 퍼즐이 주어졌을 때, 퍼즐 속에 총 몇 개의 단어가 있는지 구하는 것이다.

입력

다섯 줄에 걸쳐 5 x 5알파벳 퍼즐이 공백으로 구분되어 주어진다.

출력

첫 줄에 포함되는 총 단어 개수를 출력한다.

제한

힌트

dict.txt는 여기에 압축되어 있다.