Như mọi người nghỉ mát, bò chơi phiên bản bò của trò chữ Boggle: Coggle. Trong trò tương tự này, 25 xúc xắc chữ được tung thành ma trận như sau:

           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

Tạo từ và ghi điểm bằng cách bắt đầu ở một chữ, rồi đi đến một trong tối đa tám ô láng giềng, cho đến khi các chữ liên tiếp tạo thành từ trong từ điển.

Trong ma trận trên, "$C$" phía dưới tạo được "CAP", "COW", "COOK", nhưng không "COD" hay "PACK". Danh sách đầy đủ các từ của từ điển cho hình vuông này là "CAP", "COOK", "COW", "OWN", "WIT", "WOO", "ZOO", "ZOOM".

Chương trình phải đọc từ điển từ dict.txt. Nó xếp theo thứ tự chữ cái, có dưới 25,000 từ, mỗi từ không quá 20 ký tự. Từ điển thực được cung cấp trong tệp đính kèm dict.txt và có ở thư mục làm việc khi chấm.

Giúp Bessie xem mình làm tốt đến đâu. Đọc năm hàng, mỗi hàng năm chữ, biểu thị xúc xắc, và đếm số từ trong từ điển có thể tạo. Không dùng chữ của cùng xúc xắc hai lần trong một từ.

Đếm số từ tạo được. Có thể nhỏ hơn số cách tạo, vì một từ có thể tạo theo nhiều cách.

Dữ liệu vào

• Các dòng $1,\ldots,5$: dòng $i$ chứa năm chữ hoa cách nhau bởi dấu cách, biểu thị hàng $i$.

Dữ liệu ra

• Dòng $1$: một số nguyên, số từ trong từ điển có thể tạo theo quy tắc mô tả.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

8

Nguồn bài toán: Traditional, 2009