کنار هم چیدن قطعه‌ها

Time Limit: 48 Seconds    Memory Limit: 65536 KB

فرض کنید تعدادی قطعه‌ی چوبی با شکل‌های مختلف داده شده. هر قطعه از کنارهم قرار گرفتن تعدادی مربع 1x1 تشکیل شده، به‌طوری‌که هر مربع لااقل با یک مربع دیگر یک ضلع مشترک دارد. مثلا در شکل زیر چند قطعه‌ی نمونه نشان داده شده:

 

 

مسئله این است که برای یک m و n داده شده، آیا می‌توان با کنار هم قرار دادن این قطعه‌ها، یک مستطیلی m x n را به‌طور کامل پوشاند به‌طوری‌که که قطعه‌ها روی هم قرار نگیرند یا نه؟ برای سادگی فرض کنید که قطعه‌ها را نمی‌توان چرخاند یا پشت‌ورو کرد (به‌جز قسمت «ب»).

 

بدیهی است که اگر تعداد خانه‌های همه‌ی قطعه‌ها برابر m x n نباشد، پاسخ مسئله منفی خواهد بود ولی به‌وضوح این یک شرط لازم (و نه کافی) است. به‌عنوان نمونه اگر m=3 و n=5 باشد، با قطعه‌های بالا می‌توان یک مستطیل m x n را پوشاند:

 

 

الف) [۱۰ نمره] نشان دهید این مسئله ان‌پی-تمام است.

 

[راهنمایی: آیا می‌توانید مسئله‌ی «جمع زیرمجموعه‌ای» را به این مسئله تبدیل کنید؟ توجه کنید که تبدیل شما باید چندجمله‌ای باشد و در مسئله‌ی «جمع زیرمجموعه‌ای» برای نمایش عدد n به‌تعداد n بیت نیاز است.]

 

ب) [۵ نمره اختیاری] در مسئله‌ی فوق، اگر چرخش قطعه‌ها هم مجاز باشد، نشان دهید که مسئله کماکان ان‌پی‌-تمام است.

 

پ) [۴۰ نمره] برنامه‌ای بنویسید که با دریافت مشخصات بلوک‌ها و اعداد m و n، مشخص کند که آیا پاسخ مسئله‌ی فوق مثبت است یا نه (فرض کنید چرخش و پشت‌ورو کردن قطعه‌ها مجاز نیست). تعداد قطعه‌ها حداکثر ۱۰ و مقدار m x n حداکثر ۳۰ است. برنامه‌ی شما برای هر ورودی باید در حداکثر ۳ ثانیه پاسخ را بیابد.

 

ورودی: در خط اول ورودی، یک عدد k20 نوشته شده که تعداد مجموعه‌های ورودی است. بعد از آن برای هر مجموعه‌ی ورودی، در خط اول سه عدد p, m, n نوشته شده که p تعداد قطعه‌ها، m تعداد سطرها و n تعداد ستون‌های مستطیل است. سپس در p خط بعدی، هر خط مشخصات یک بلوک را دارد که با عدد c، برابر با تعداد خانه‌های آن قطعه، شروع می‌شود و بعد از آن 2c عدد صحیح نوشته شده که هر زوج مختصات یک قطعه را نشان می‌دهد (ابتدا شماره‌ی سطر بعد ستون). فرض کنید که مختصات اولین خانه همیشه (0, 0) است و مختصات بقیه‌ی خانه‌ها به نسبت خانه‌ی اول داده شده.

 

خروجی: به ازاء هر مجموعه‌ی ورودی، یک خط خروجی وجود دارد که شامل 0 یا 1 است. پاسخ 1 را به‌عنوان «آری» و 0 را به‌عنوان «خیر» بنویسید.

 

 

Sample Input

2
3 2 4
2 0 0 1 0
2 0 0 1 0
4 0 0 1 0 1 -1 1 -2
4 3 5
5 0 0 0 1 1 1 2 0 2 1
5 0 0 1 -1 1 0 1 1 2 0
3 0 0 0 1 1 0
2 0 0 0 1

Sample Output

0
1

Submit