Ne amintim cu toţii jocul „avioane” pe care în jucam la şcoală, în pauze, cu colega de bancă. În problema noastră jocul se desfăşoară pe o suprafaţă cu N linii şi N coloane. Un “avion” este o piesă care ocupă poziţii de pe suprafaţa de joc dispuse exact în ordinea:
x
x
x
x
x
x
x
x
x
x
x
Valorile marcate cu x aparţin avionului, iar celelalte nu. Sunt acceptate şi celelalte trei configuraţii ce se obţin prin rotirea poziţiei date cu 90, 180, 270 grade. Suprafaţa de joc are unele poziţii care nu pot fi ocupate de un avion.
Cerinţă
În problema noastră se cunoaşte dimensiunea suprafeţei pătrate şi configuraţia sa şi se cere determinarea numărului maxim de avioane ce se pot aşeza, precum şi o modalitate de aşezare a acestui număr maxim.
Date de intrare
Fişierul avioane.in are pe prima linie un număr natural N, dimensiunea suprafeţei. Pe fiecare dintre următoarele N linii sunt câte N valori întregi din mulţimea {0,-2} separate prin câte un spaţiu. Valoarea 0 reprezintă poziţie ce poate fi ocupată de un avion, iar valoarea -2 o poziţie ce nu poate fi ocupată.
Date de ieşire
În fişierul avioane.out, pe prima linie se va scrie numărul maxim de avioane ce se pot aşeza, notat cu M. Pe următoarele N linii se găsesc câte N numere întregi separate prin câte un spaţiu ce pot avea valorile: -2, 0, 1, 2, …, M. Valoarea i (1<=i<=M) se găseşte exact pe poziţiile ocupate de avionul i. Elementele de pe poziţiile neocupate de avioane au exact valorile corepunzătoare poziţiei respective din fişierul de intrare.
Restricţii
5 <= N <= 10
avioanele trebuie aşezate complet în interiorul suprafeţei;
o poziţie de pe suprafaţă poate fi ocupată de cel mult un avion;
dacă sunt mai multe aşezări posibile cu număr maxim de avioane se poate afişa configuraţia corespunzătoare oricăreia dintre ele;
valorile scrise pe aceeaşi linie in fişierele de intrare/ieşire sunt separate prin spaţii.