Wie alle im Urlaub spielen die Kühe ihre Version des Wortspiels Boggle: Coggle. In diesem ähnlichen Spiel werden 25 Buchstabenwürfel in eine Matrix wie diese geworfen:

           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

Wörter und damit Punkte entstehen, indem man bei einem Buchstaben beginnt und jeweils zu einem seiner bis zu acht Nachbarn geht, bis die aufeinanderfolgenden Buchstaben ein Wörterbuchwort ergeben.

In der obigen Matrix kann man mit dem unteren "$C$" die Wörter "CAP", "COW" und "COOK" bilden, aber nicht "COD" oder "PACK". Die vollständige Liste der Wörterbuchwörter für dieses Quadrat ist "CAP", "COOK", "COW", "OWN", "WIT", "WOO", "ZOO" und "ZOOM".

Dein Programm soll das Wörterbuch aus dict.txt lesen. Es ist alphabetisch geordnet, enthält weniger als 25,000 Wörter und jedes hat höchstens 20 Zeichen. Das tatsächliche Wörterbuch wird als Anhang dict.txt bereitgestellt und liegt während der Bewertung im Arbeitsverzeichnis.

Hilf Bessie, ihr Ergebnis festzustellen. Lies fünf Zeilen mit jeweils fünf Buchstaben für die Würfel und bestimme die Anzahl bildbarer Wörterbuchwörter. Verwende keinen Würfelbuchstaben zweimal im selben Wort.

Zähle die bildbaren Wörter. Das können weniger sein als die Möglichkeiten ihrer Bildung, da ein Wort auf mehrere Arten entstehen kann.

Eingabe

• Zeilen $1,\ldots,5$: Zeile $i$ enthält fünf durch Leerzeichen getrennte Großbuchstaben für Reihe $i$.

Ausgabe

• Zeile $1$: eine ganze Zahl, die Anzahl nach den beschriebenen Regeln bildbarer Wörterbuchwörter.

Beispiele

Eingabe 1

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

Ausgabe 1

8

Aufgabenquelle: Traditional, 2009