Условие
Дано поле не больше 20 x 20 и набор русских слов в верхнем регистре. Нужно построить кроссворд, используя любое подмножество слов из входного набора.
Правила:
1. Размер готовой сетки не должен превышать размеры M x N из входа.
2. Можно использовать любое подмножество слов, но каждое размещенное слово должно идти по горизонтали или вертикали.
3. Judge читает слова только слева направо и сверху вниз.
4. Каждое размещенное слово должно пересекаться хотя бы с одним другим словом.
5. Все занятые клетки должны образовывать ровно одну компоненту связности.
6. Буквы разных слов не могут стоять в соседних клетках по вертикали или горизонтали без пересечения.
За каждый тест начисляется столько баллов, сколько корректных пересечений найдено в сетке. Итог за решение — это сумма баллов по всем открытым и скрытым тестам.
Формат ввода
Первая строка содержит M N — максимальную высоту и ширину поля.
Вторая строка содержит K — количество слов.
Далее идут K слов в верхнем регистре, по одному в строке.
Формат вывода
В первой строке выведите H W — высоту и ширину решетки.
Затем выведите H строк длины W. В каждой клетке должна быть заглавная буква или символ ".".
Дополнительно поддерживается формат:
`очки слова пересечения`
и затем ровно M строк поля. Judge перепроверит эти числа сам.
Примечания
Открытых тестов ровно 10, скрытых тестов тоже 10. Все встроенные наборы конструктивно решаемы, но баллы платформа считает автоматически только по числу пересечений.
Пример ввода
13 13 6 АЛГОРИТМИКА АНАЛИЗ ГРАФЫ РЕКУРСИЯ ТЕОРЕМА ИНВАРИАНТ
Пример вывода
9 11 АЛГОРИТМИКА Н.Р.Е.Е.Н.. А.А.К.О.В.. Л.Ф.У.Р.А.. И.Ы.Р.Е.Р.. З...С.М.И.. ....И.А.А.. ....Я...Н.. ........Т..