0002. Ключ

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

Петя после учебы пошел домой. Но придя домой он с ужасом узнал, что в гардеробе ему дали не его куртку. Посмотрев содержимое карманов, он нашел там K ключей. Внимательно изучив ключи и замочную скважину, он пришел к выводу, что подбирать ключ к двери он будет до утра (если вообще такой найдется). Поэтому он попросил вас определить, какие ключи могут подойти, а какие нет.

Для этого Петя зарисовал сечение замочной скважины и всех ключей. Замочная скважина описывается матрицей из N строк по M элементов, точек ('.') или звездочек ('*'). При этом '.' обозначает отверстие. Сечение каждого ключа описывается аналогично. Ключи можно поворачивать на 90, 180 или 270 градусов и двигать. При этом можно считать ключ подходящим, если каким-то способом сечение ключа накладывается на сечение замочной скважины без наложений звездочек. Гарантируется, что все сечения представляют собой две неразрывные области, одна из звездочек, другая из точек. Также гарантируется, что в сечениях ключей все звездочки находятся внутри (нет звездочек в перовых и последних строках и столбцах), а в сечении замочной скважины - все точки внутри. В сечениях ключей есть хотя бы 1 звездочка, а в сечении замочной скважины - хотя бы 1 точка.

Формат входного файла

В первой строке 3 числа N, M и K (3 ≤ N ≤ 20, 3 ≤ M ≤ 20, 1 ≤ K ≤ 10). Далее следует описание сечения замочной скважины и сечений K ключей. Каждое сечение описывается N строчками по M символов - '*' и '.'. Между описаниями сечений есть одна пустая строка.

Формат выходного файла

Единственная строка выходного файла должна содержать номера подходящих ключей в порядке возрастания.

Пример:

input.txtoutput.txt
5 6 3 ****** ***.** *....* **.*** ****** ...... ...*.. .****. ..*... ...... ...... .**... ..**.. ..*... ...... ...... ..*... .****. ...*.. ...... 1 2


Источник: Районная олимпиада РК по информатике, 2007.

Обсудить       Отправить решение



Версия для печати