Rezolvare PBinfo #384

Cerinţa

Se consideră o tablă de şah cu n linii şi m coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L).

Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu n linii și m coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau 0, dacă nu s-a ajuns.

Date de intrare

Fișierul de intrare saritura_calului1.in conține numerele n şi m , apoi numere x y, reprezentând dimensiunile tablei (numărul de linii şi numărul de coloane) , respectiv coordonatele iniţiale ale calului (linie, coloana).

Date de ieşire

Fișierul de ieșire saritura_calului1.out va conține n linii cu câte m numere naturale cuprinse între 1 și n*m, separate prin exact un spațiu, reprezentând parcurgerea solicitată.

Restricţii şi precizări

• 1 ≤ n,m ≤ 100
• 1 ≤ istart ≤ n
• 1 ≤ jstart ≤ m
• scorul obținut pe fiecare test este proporțional cu gradul de acoperire a tablei. Astfel, dacă tabla este acoperită în întregime, se acordă 100% din punctaj. Dacă tabla este acoperită în proporție de 70%, se acordă 70% din punctaj, etc.

Exemplul 1

saritura_calului1.in

4 5 1 1

saritura_calului1.out

1 12 7 16 3 
6 17 2 11 8 
13 10 19 4 15 
18 5 14 9 20

Explicație

Parcurgerea este completă, se va acorda 100% din punctaj.

Exemplul 2

saritura_calului1.in

4 5 1 1

saritura_calului1.out

1 12 7 16 3 
6 0 2 11 8 
13 10 0 4 15 
0 5 14 9 0

Explicație

Parcurgerea este parțială. S-au făcut 16 pași din 20, se va acorda 80% din punctaj.