Under construction

Still being built. Things may change

Word Puzzle

Time limit2sMemory limit128 MB

Summary
Count how many words from a fixed dictionary can be spelled by paths of adjacent, non-repeating cells in a 5x5 letter grid.
Level

Medium6 of 10

Topics
Trie, Backtracking, DFS, Matrix
Solved
No attempts yet

Problem

A 5 x 5 grid contains one uppercase English letter in each cell. Determine how many words from the fixed dictionary dict.txt can be formed in the grid.

To form a word, choose any starting cell and repeatedly move to one of the 8 neighboring cells, appending each letter you visit. The same cell cannot be used more than once while forming one word. If the same dictionary word can be formed by multiple paths, count it only once.

Input

Five lines are given. Each line contains 5 uppercase English letters separated by spaces, describing the 5 x 5 puzzle.

Output

Print one integer: the total number of dictionary words that can be formed in the puzzle.

Hint

The fixed dictionary file for this problem is included as dict.txt.

Examples1

  1. Example 1

    Input
    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
    Expected output
    8