Printre multele sale hobby-uri, Vasilică este pasionat și de puzzle-uri. Recent, el a descoperit un program cu care poate transforma orice imagine într-un puzzle cu piese pătrate. Programul ia o imagine, o decupează în piese pătrate pe care apoi le rotește și le amestecă, rezultând o nouă imagine.
Din păcate, versiunea demo a programului nu-i permite să și reconstituie imaginea, și cum până la bursă mai e ceva, Vasilică s-a hotărât să facă singur un program care să rezolve puzzle-urile generate de versiunea demo.
Programul pe care Vasilică vrea să-l realizeze – cu ajutorul vostru – trebuie să poată determina poziția și rotația pieselor de puzzle plecând de la imaginea originală și de la o imagine realizată din piese amestecate. Pentru început Vasilică vrea să rezolve doar puzzle-uri grayscale (în alb/negru). Astfel, se consideră că o imagine este formată din Lung x lat pixeli (puncte), fiecare putând fi colorat într-o tentă de gri. Pentru acest caz, se consideră că un punct poate avea doar 256 de tente posibile. Prin convenție, albul este reprezentat cu valoarea 255, iar negrul cu valoarea 0, celelalte nuanțe de gri fiind reprezentate prin valori intermediare (1-254)
Se va realiza un program C care, primind la intrare o matrice reprezentând imaginea originală și o matrice reprezentând imaginea formată din piesele amestecate va produce la ieșire un șir de tupluri(poziție_în_puzzle, poziție_în_original, rotație) reprezentând poziția și rotația pieselor pentru a obține imaginea originală. Șirul va fi ordonat după poziție_în_puzzle.
Datele de intrare se vor citi de la intrarea standard (stdin) și se vor afișa la ieșirea standard (stdout) folosind redirectări de fișiere.
Formatul acestor date este prezentat în secțiunile următoare.
Atenție! – Respectați formatul de intrare și cel de ieșire al datelor. Testarea funcțională se va face cu un evaluator automat.
Date de intrare
Datele se vor citi de la tastatură (sau dintr-un fișier folosind redirectări de consolă) și vor avea următoarea formă:
pe primul rând două valori întregi reprezentând lățimea W și înălțimea H a imaginii
pe al doilea rând o valoare întreagă reprezentând latura P a unei piese de puzzle
pe următoarele H rânduri câte W valori naturale între 0-255 reprezentând pixelii din imaginea originală
pe următoarele H rânduri câte W valori naturale între 0-255 reprezentând pixelii din imaginea amestecată
Se impun următoarele restricții pentru valorile de intrare:
atât W cât și H să fie mai mici sau egale cu 512
valoarea P să dividă atât W cât și H (nu se acceptă fracțiuni de piesă)
valoarea P trebuie să fie mai mare decât 1
valorile pixelilor să fie în intervalul specificat
Vor exista teste în care aceste restricții nu vor fi respectate. În acest caz programul va trebui să afișeze un mesaj de eroare și să iasă cu valoarea 1. Se va folosi în acest sens ori apelul return 1; ori funcția exit() (pentru care trebuie inclus fișierul <stdlib.h>.
În caz de succes, programul va afișa datele de ieșire după specificația următoare și va returna către sistemul de operare valoarea 0 (return 0;)
În cazul în care datele de intrare sunt corecte se va afișa o listă cu piesele de puzzle și poziționarea lor (poziție și rotație), astfel:
un număr de
linii (numărul de piese din puzzle) conținând trei valori întregi cu următoarea semnificație:poziția piesei în imaginea amestecată
poziția piesei în imaginea originală
rotația piesei, codificată astfel:
0 – piesă nerotită
1 – piesă rotită 90 de grade în sens orar
2 – piesă rotită 180 de grade în sens orar
3 – piesă rotită 270 de grade în sens orar
Rotația piesei se referă la unghiul cu care trebuie rotită piesa din imaginea amestecată pentru a obține piesa din imaginea originală.
Poziția unei piese se va determina prin numărare, de la stânga la dreapta și de sus în jos, ca în figură:
Exemple de date
Fie următoarele date de intrare:
4 4 2 123 59 95 136 186 83 220 29 121 18 92 151 93 209 5 216 59 83 209 93 123 186 18 121 216 5 136 29 151 92 95 220
Datele de ieșire trebuie să fie următoarele:
0 0 1 1 2 2 2 3 2 3 1 1
Data: 30.11.2008