printРабочее место участника

printЗадачи

1316. Кроссворд

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Кроссворд является сформированным правильно, если
  • все слова в нем состоят не менее чем из 2 букв,
  • если две буквы находятся в соседних клетках, то они являются частью какого-либо слова,
  • слова, читаемые по горизонтали, начинаются только с клеток, у которых нет слева клетки с буквой, а слова, читаемые по вертикали, начинаются с клеток, у которых нет выше клетки с буквой.
Каждая буква в правильном кроссворде была заменена некоторым целым числом. При этом каждой букве соответствует свое число, а каждому числу соответствует одна буква. Известны все слова, использованные в кроссворде. Требуется расставить слова в сетке кроссворда (восстановить кроссворд).
Во входном файле в первой строке содержатся два целых числа `n` и `m` (`1\ ≤\ n\ ≤\ 20`, `1\ ≤\ m\ ≤\ 20`) – размеры кроссворда, далее следует `n` строк, содержащих по `m` целых чисел (от 0 до 26) в строке. Число 0 соответствует незаполненной (черной) клетке кроссворда. Далее следуют все слова, используемые в кроссворде, по одному слову в каждой строке. Слова содержат только прописные латинские буквы. Длина всех слов кроссворда – от 2 до 20 символов.
В выходной файл вывести заполненный кроссворд. Если возможно несколько вариантов заполнения, то нужно вывести любой (один) из них. Для обозначения незаполненных клеток используйте символ '.' (точка).

Пример ввода

3 4
7 1 2 5
0 4 0 14
14 5 8 0
ICE
ET
TEA
FILE

Пример вывода

FILE
.C.T
TEA.
loading