گلدان‌های ل‌-شکل


عادل یک گلخانه‌ی m×nm \times n دارد که در kk تا از خانه‌های آن کلمات جدید پرورش می‌دهد. اخیرا وی با تکنولوژی جدید گلدان‌هایی یافته که به شکل حروف LL انگلیسی هستند و در آن کلمات سریعتر رشد می‌کند. اما چون عادل به حروف فارسی علاقمند است، به جای آن از گلدان‌های تولید داخل ل شکل استفاده می‌کند که دقیقا همان شکل گلدان‌های قبلی هستند ولی فارسی هستند. یک گلدان ل شکل از چهار مربع تشکیل شده و به یکی از ۸ شکل زیر است:

گلدان‌های ل شکل

حال عادل می‌خواهد ببیند به چند طریق می‌تواند گلخانه را با استفاده از گلدان‌های جدید پر کند به طوری که همه‌ی خانه‌ها پوشانده شوند، هیچ خانه‌ای که قبلا پر بود دوباره پوشانده نشود و هیچ دو گلدانی همپوشانی نداشته باشند؟ به عادل کمک کنید.

ورودی🔗

در خط اول ورودی 1n,m151\leq n,m \leq 15 اندازه‌های جدول داده می‌شوند. در nn خط بعدی،‌ در هر خط mm کاراکتر '.' یا '#' ظاهر می‌شود که . به معنای خانه‌ی خالی و # به معنای خانه‌ی از قبل پر‌شده است.

خروجی🔗

در تنها خط خروجی باید تعداد راه‌های پرکردن جدول را چاپ کنید. اگر هیچ راهی وجود نداشت صفر چاپ کنید. تضمین می شود تعداد راه های پر کردن جدول کمتر از یک میلیون است !!

مثال🔗

ورودی نمونه 1

3 2
# .
# .
. .
Plain text

خروجی نمونه 1

1
Plain text

ورودی نمونه 2

4 4
# # # #
# # # #
. . . .
. . . .
Plain text

خروجی نمونه 2

2
Plain text

ورودی نمونه 3

3 3
. . .
. . .
. . .
Plain text

خروجی نمونه 3

0
Plain text

توضیح🔗

در مثال سوم از آنجا که ۹ خانه‌ی خالی داریم و هر گلدان ۴ خانه را می‌پوشاند نمی‌توان با گلدان همه‌ی خانه‌ها را پوشاند. در مثال دوم به دو شکل می‌توان با گلدان‌ها جدول را پوشاند:

1 1 1 2
1 2 2 2
Plain text

و

1 2 2 2
1 1 1 2
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.