Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 04 Mar 2021 02:28:20

Банк задач


Номер задачи - 4

Задача Полимино

Ограничение - 1 сек. на один тест

Толик увлекается полимино и его интересуют связанные сними вопросы.

Полимино - это фигура, составленная из квадратов так, чтобы их можно было обойти ходом ладьи. На рисунке приведены несколько примеров полимино.

Для своих экспериментов Толик вырезает полимино из бумаги или из полимино, оставшихся после предыдущих попыток. Поэтому его интересует, сколько существует способов вырезать одно полимино из другого. При этом размер клеток исходного полимино может быть в K раз больше размера клеток требуемого полимино. Тогда Толик делит каждую клетку исходного полимино на K2 клеток и вырезает требуемое полимино по границам получившихся клеток.

Формат входных данных

Первая строка входного файла содержит число K (1 <= K <= 10000), далее следуют описания двух полимино, сначала требуемого, затем исходного.

Полимино описывается следующим образом. Первая строка описания содержит задано два числа: H и W - высота и ширина полимино. Последующие H строк содержат по W символов каждый. Клетки принадлежащие полимино помечена символом <X>, а не принадлежащие - символом <.> (точка). Каждое из полимино содержат не более 300 клеток.

Формат выходных данных

Выходной файл должен содержать одно число - количество различных способов вырезать требуемое полимино из исходного, увеличенного в K раз.

Примеры
stdin stdout
2
2 2
XX
XX
2 3
XXX
.X.
7
Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.