پر کردن مربع

یک مربع با اندازهٔ n در n (طول و عرض) داریم که می‌خواهیم با n * n مربع کوچک با اندازهٔ واحد آن را پر کنیم. هر کدام از مربع‌های کوچک هر کدام از اضلاعشان یا خط صاف هست یا روی اضلاعشان تورفتگی یا بیرون رفتگی دارند. (شکل را ببینید.) چگونه مربع‌های کوچک‌تر را کنار هم بچینیم تا مربع بزرگ را به طور کامل بپوشانند؟

ورودی‌ها

کاربر در خط اول عدد n برابر طول ضلع مربع بزرگتر را وارد می‌کند.

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

مثال زیر یک نمونه از ورودی ممکن برای این برنامه است: 

2
1 -1 0 0
0 0 -1 0
-1 0 0 1
0 0 1 0

در مثال بالا در خط اول عدد ۲ را وارد کردیم پس مربع بزرگترمان ۲ در ۲ هست و چهار تا مربع کوچک‌تر داریم که اطلاعات آن‌ها را در چهار خط بعد وارد کردیم.

در خط دوم اطلاعات اولین مربع کوچک‌تر را با ‎1 -1 0 0‎ مشخص کردیم. یعنی اولین مربع ضلع بالای آن بیرون‌زدگی دارد. ضلع سمت راست آن تورفتگی دارد. ضلع پایین و چپ آن هم صاف هستند.

اگر مربع‌های فوق را طوری کنار هم بچینیم که خواستهٔ سوال محقق شود مربع بزرگتر به شکل زیر با چهار مربع کوچک‌تر ذکر شده در صورت سوال پر خواهد شد:

خروجی

در خروجی برنامه یک لیست باید return کنید که n عضو لیست دارد و هر کدام از این لیست‌ها n عضو تاپل دارند. لیست اول نمایندهٔ مربع بزرگتر، هر کدام از اعضای آن که n لیست دیگر هستند نمایندهٔ هر خط مربع و n تاپلی که داخل هر کدام این لیست‌ها هستند نمایندهٔ یک مربع هستند. مثلا برای مثال بالا که شکل آن رسم شده خروجی برنامه لیست زیر خواهد بود: 

[[(00, 00, -1, 00) (00, 00, 01, 00)]
 [(01, -1, 00, 00) (-1, 00, 00, 01)]]

اگر با مربع‌های کوچک‌تر داده شده پر کردن مربع بزرگتر ممکن نیست در خروجی String زیر را return کنید: 

No Possible Answer For The Given Input.

تست‌کیس‌ها

ورودی نمونهخروجی نمونه 
3
0 1 0 0
0 1 0 -1
0 0 -1 -1
0 0 -1 0
0 0 0 0
1 0 -1 0
1 0 0 0
0 -1 0 0
1 0 0 1

[[(00, 01, 00, 00) (00, 01, 00, -1) (00, 00, -1, -1)]
 [(00, 00, -1, 00) (00, 00, 00, 00) (01, 00, -1, 00)]
 [(01, 00, 00, 00) (00, -1, 00, 00) (01, 00, 00, 01)]]

2
0 0 -1 0
0 0 0 0
1 1 0 0
0 0 0 -1

[[(00, 00, -1, 00) (00, 00, 00, 00)]
 [(01, 01, 00, 00) (00, 00, 00, -1)]]

توجه

  • برای سادگی فرض کنید که امکان چرخاندن مربع‌های کوچک‌تر وجود ندارد.
  • برای این تمرین یک فایل زیپ آپلود شده که باید آن را دانلود کنید. سپس آن را از حالت فشرده خارج کنید و داخل PyCharm پوشهٔ extract شده را به عنوان فولدر پروژه باز کنید. سپس در تنظیمات run پایچارم آدرس فایل main.py را مشخص کنید تا برنامه را بتوانید اجرا کنید. سپس محتویات فایل requirements.txt را روی پروژهٔ ایجاد شده نصب کنید. square_packing.zip
  • پیش از نوشتن کد باید محتوای فایل main.py و problem.py را کامل بخوانید. کد نوشته شده در فایل problem.py یک بازنمایی (representation) از صورت سوال هست. در فایل main.py هم فقط فایل‌های problem.py و solution.py را ایمپورت و بعد توابع آن‌ها را call کردیم.
  • بعد از انجام مراحل فوق فایل solution.py را باز کنید و کدتان را درون آن بنویسید.
  • برای چاپ لیست خروجی برنامه با فرمت مشخص شده در صورت تمرین که حالت جدولی دارد باید از تابع matrix از کتابخانهٔ numpy استفاده کنید. پس ابتدا باید این کتابخانه را نصب و import کنید. برای نصب این پکیج از فایل requirements.txt کمک بگیرید. همچنین برای پرینت اعداد 1 و 0 و ‎-1 در خروجی برنامه با دو رقم یعنی به صورت 01 و 00 و ‎-1 از String Formatting استفاده کنید. برای اینکار داخل string خروجی برنامه از placeholder به صورت {:02d} استفاده کنید.
  • برای درک بهتر کد و کاربرد متغیرها در آن بعد از باز کردن برنامه در PyCharm یکبار آن را در Debug Mode اجرا کنید.