Clasa a IX-a
Ziua 2
Problema 6

Planeta "Cubulet"

Planeta "Cubulet" este acoperita numai din roci de forma cubica de aceeasi dimensiune. O harta de dimensiune mxn ne da configuratia planetei.
Cubuletele sunt asezate pe linii, coloane si pe verticala, perfect suprapuse, pornind de la nivelul 0.
Un asteroid, format si el numai din cubulete de aceeasi dimensiune, are o forma descrisa astfel:
- consideram un plan ca fiind nivelul 0;
- pe acest plan sunt plasate cubulete pe linii, pe coloane si pe verticala, atat in partea de sus cat si in partea de jos a planului;
- toate cubuletele formeaza un singur corp.
Asteroidul poate efectua rotiri in spatiu:
- pe verticala pe directia Nord-Sud cu 180 grade;
- pe orizontala cu cate 90 de grade spre dreapta.
Se cere sa se gaseasca o asezare a corpului pe suprafata planetei, astfel incat toate fetele cubuletelor orientate spre planeta sa intre in contact cu suprafata planetei.

Date de intrare:
Fisierul harta.in contine configuratia suprafetei planetei m n   - numarul de linii si respectiv coloane (1<=m, n<=70) a(1,1) a(1,2) a(1,n)  - a(I,j) reprezinta numarul de cubulete pe verticala in pozitia I,j 0=a(I,j)=70
...
a(m,1) a(m,2) a(m,n)
Fisierul corp.in contine pe mai multe linii datele referitoare la forma asteroidlui, o linie are structura:
I j sus jos
unde:
I este linia, j coloana, numerotate de la cel mai de sus, respectiv de la cel mai din stanga cubulet al asteroidului, vazut in sectiune orizontala. (I,j<=min(m,n)).
sus - numarul de cubulete pe verticala in sus pornind de la nivelul 0 (0<=sus<=70)
jos - numarul de cubulete pe verticala in jos pornind de la nivelul 0 (0<=jos<=70).

Date de iesire:
Fisierul harta.out va contine pe prima linie o succesiune de caractere N, V, reprezentind operatiile de Nerotire, rotire Verticala, respectiv rotire Orizontala a asteroidului si, pe urmatoarele linii, noua harta a planetei. Daca asteroidul nu se poate plasa pe planeta fisierul va contine o singura linie cu mesajul NU.

Exemplu:

harta.in
4 5
2 7 4 5 1
1 2 3 5 1
3 2 1 4 3
2 1 3 3 1
corp.in
1 2 0 2
2 2 1 0
2 3 4 3
3 1 4 4
3 2 2 1
2 4 3 2
harta.out
OVO
2 7 4 5 1
1 2 3 7 1
3 7 8 5 3
2 1 3 6 9

Timp de executie pentru fiecare test maxim 3 sec.
Punctaj maxim posibil: 50 puncte