Я думаю, что Вы являетесь большим поклонником настольной игры "Боггл". Не волнуйтесь, если Вы не знакомы с ее правилами, я их Вам объясню. Боггл представляет собой 4×4 сетку из букв, в которой Вам следует найти как можно больше букв. Если я играю в Боггл со своей женой (или против нее), она всегда выигрывает — проигравший (это я) всегда должен делать работу по дому, как например выносить мусор. Помогите мне выиграть.
Слова в Боггл конструируются из соседних букв (по горизонтали, вертикали и диагонали), но одна клетка может использоваться в слове только один раз. Только слова, представленные в словаре, являются корректными.
Слова из 3 или 4 букв стоят 1 балл, слова из 5 букв стоят 2 балла, 6 букв 3 балла, 7 букв 5 балов. 8 буквенные слова стоят 11 баллов. Если Вы найдете более одного слова (я надеюсь, что это будет так), то баллы за них суммируются.
Первая строка содержит количество слов w (1<w<300000) в словаре. Каждая из следующих w строк содержит одно слово. Слова содержат до 8 букв верхнего регистра ('A' — 'Z'). После задания словаря идет пустая строка. В следующей строке задано количество досок b (1<b<30) Боггл. Каждая доска представляет собой сетку 4×4 букв верхнего регистра в четырех строках. Доски Боггл между собой разделены пустой строкой.
Для каждой доски выведите максимальную возможную сумму баллов, самое длинное слово и количество найденных слов. Слова, встречающиеся дважды (или более раз) в одном Боггл, считаются один раз. Если существует несколько самых длинных слов, вывести лексикографически наименьшее. Считайте, что каждый Боггл содержит как минимум одно корректное слово.