ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1519. Формула 1

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Несмотря на то, что Вологда не добилась права проведения Олимпийских Игр 20** года, как всем уже стало известно, она будет принимать один из этапов Гран-при Формулы 1. Конечно, для такого ответственного мероприятия надо построить новую трассу, а также гостиницы, рестораны, международный аэропорт и всё остальное, что может понадобиться болельщикам, которые вскоре наводнят Вологду. Но когда все гостиницы и половина ресторанов были уже построены, выяснилось, что на месте будущей гоночной трассы помимо рабочих в вагончиках живут ещё и суслики в норках. Так как мы все любим животных, экологи ни за что не позволят укладывать трассу поверх нор. И вот теперь мэр сидит в своём кабинете, грустно склонившись над картой будущей трассы, на которую нанесены обиталища ненавистных сусликов.

Задача

Кто же сможет нарисовать план трассы и тем самым спасти город от неминуемого позора? Мэру помогут лишь настоящие профессионалы своего дела, закалённые в боях программисты из местного технического вуза! Весь город устремил свои взоры на первую команду политеха. Но так как наши герои не ищут лёгких путей, они решили поставить себе гораздо более сложную задачу: «Наверняка мэр очень обрадуется, если мы найдём, сколько всего трасс можно построить на данном участке!»
Надо сказать, что трасса в Вологде будет устроена довольно просто. Это прямоугольник размерами N*M, через каждую клетку которого проходит ровно один участок трассы. Дорога всегда должна идти параллельно одной из сторон исходного прямоугольника, так что повороты возможны лишь под прямым углом. На рисунке ниже приведены два примера при N = M = 4 (серые квадраты – норы сусликов, жирная чёрная линия – трасса). Других способов построить трассу при таком расположении нор нет.
Problem illustration

Исходные данные

Первая строка содержит целые числа N и M (2 ≤ N, M ≤ 12). Каждая из следующих N строк содержит M символов – соответствующие клетки прямоугольника. Символ «.» (точка) обозначает клетку, через которую нужно проложить трассу, а символ «*» (звёздочка) – клетку, где находится норка суслика. Гарантируется, что есть хотя бы 4 клетки, через которые можно проложить трассу.

Результат

Вывести искомое количество способов. Гарантируется, что оно не превышает 263-1.

Примеры

исходные данныерезультат
4 4
**..
....
....
....
2
4 4
....
....
....
....
6
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge