یک مربع با اندازهٔ 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.
ورودی نمونه | خروجی نمونه |
---|---|
|
|
|
|