단어 퍼즐

5 x 5 격자에 대문자 알파벳이 한 글자씩 들어 있다. 고정된 사전 dict.txt에 있는 단어 중, 이 격자에서 만들 수 있는 단어가 총 몇 개인지 구하여라.

단어는 임의의 칸에서 시작해 인접한 8방향 중 하나로 이동하며 글자를 이어 붙여 만든다. 한 단어를 만드는 동안 같은 칸을 두 번 이상 사용할 수 없다. 같은 단어를 만들 수 있는 경로가 여러 개여도 그 단어는 한 번만 센다.

다섯 줄에 걸쳐 5 x 5 알파벳 퍼즐이 주어진다. 각 줄에는 대문자 알파벳 5개가 공백으로 구분되어 있다.

퍼즐에서 만들 수 있는 사전 단어의 총 개수를 한 줄에 출력한다.

이 문제에서 사용하는 고정 사전 파일은 dict.txt에 들어 있다.