casa

Casa

== include(page="template/taskheader" task_id="casa") ==

În această poveste este vorba despre o casă cu mai multe camere. O cameră are forma unui pătrat de latură 1. Dacă două camere au un perete comun, atunci se poate trece dintr-o cameră în alta. Casa nu are neapărat formă dreptunghiulară.

În această poveste este vorba despre o casă cu mai multe camere. O cameră are forma unui pătrat de latură $1$. Dacă două camere au un perete comun, atunci se poate trece dintr-o cameră în alta. Casa nu are neapărat formă dreptunghiulară.

O asemenea casă poate fi descrisă în povestea noastră în două moduri:

* prin _matricea minimală_: o matrice cu elemente *0 şi 1* în care există *N* valori egale cu *1*, ce corespund camerelor, iar prima linie, ultima linie, prima coloană şi ultima coloană au cel puţin un element egal cu 1.
* prin _construcţie_: un şir de *N-1 perechi* (a ~i~, b ~i~)1≤i<n în care a ~i~ ∈ {1,2,…,i} şi b ~i~ ∈ {N, S, E, V}. Camerele vor fi numerotate de la 1 la n. Perechea (a ~i~, b ~i~) precizează poziţia camerei i+1 faţă de camera a ~i~: E înseamnă la dreapta (est), N deasupra (nord), V la stânga (vest), S dedesubt (sud). Observaţi că pentru prima cameră nu există nicio precizare!

* prin _matricea minimală_: o matrice cu elemente *0 şi 1* în care există *N* valori egale cu *1*, ce corespund camerelor, iar prima linie, ultima linie, prima coloană şi ultima coloană au cel puţin un element egal cu $1$.
* prin _construcţie_: un şir de *N-1 perechi* $(a ~i~, b ~i~)1≤i<n$ în care $a ~i~ ∈ {1,2,…,i}$ şi $b ~i~ ∈ {N, S, E, V}$. Camerele vor fi numerotate de la $1$ la $n$. Perechea $(a ~i~, b ~i~)$ precizează poziţia camerei $i+1$ faţă de camera $a ~i~$: $E$ înseamnă la dreapta (est), $N$ deasupra (nord), $V$ la stânga (vest), $S$ dedesubt (sud). Observaţi că pentru prima cameră nu există nicio precizare!

!problema/casa?casa_image1.png!

De exemplu, casa de mai sus poate fi descrisă de şirul (1 E) (2 E) (2 S) (3 S), adică a doua cameră e “lipită” la est de prima cameră, următoarea (a treia) la est de camera 2, a patra la sud de camera 2, iar ultima la sud de camera 3.

De exemplu, casa de mai sus poate fi descrisă de şirul $(1 E) (2 E) (2 S) (3 S)$, adică a doua cameră e “lipită” la est de prima cameră, următoarea (a treia) la est de camera $2$, a patra la sud de camera $2$, iar ultima la sud de camera $3$.

h2. Cerinta

h2. Date de ieşire
* Dacă valoarea lui *p este 1* atunci *se va rezolva numai cerinţa 1*. În acest caz fişierul *casa.out* va conţine pe prima linie două numere naturale *M şi N*, separate prin câte un singur spaţiu reprezentând numărul de linii respectiv numărul de coloane ale matricei minimale, iar pe următoarele *M* linii câte *N* valori *0 sau 1* separate prin câte *un singur spaţiu*.

* Dacă valoarea lui *p este 2* atunci *se va rezolva numai cerinţa 2*. În acest caz fişierul *casa.out* va conţine pe prima linie două numere naturale *Nr* şi *C* separate printr-un singur spaţiu. *Nr* reprezintă numărul de camere, iar *C* poziţia camerei 1 (cel mai mic număr de ordine al unei coloane care conţine valoarea 1 în prima linie). Următoarele *Nr-1* linii vor conţine fiecare câte două valori separate printr-un singur spaţiu, reprezentând descrierea unei case _prin construcţie_ conform precizărilor din enunţ. Coloanele vor fi numerotate începând de la 1, iar dacă există mai multe soluţii va fi afişată cea mai mică în ordine lexicografică: perechea *(k, l)* va fi afişată înaintea perechii *(k’, l’)* dacă k < k’ sau dacă k = k’ şi l < l’ *(adică E < N < S < V)*.

* Dacă valoarea lui *p este 2* atunci *se va rezolva numai cerinţa 2*. În acest caz fişierul *casa.out* va conţine pe prima linie două numere naturale *Nr* şi *C* separate printr-un singur spaţiu. *Nr* reprezintă numărul de camere, iar *C* poziţia camerei 1 (cel mai mic număr de ordine al unei coloane care conţine valoarea 1 în prima linie). Următoarele *Nr-1* linii vor conţine fiecare câte două valori separate printr-un singur spaţiu, reprezentând descrierea unei case _prin construcţie_ conform precizărilor din enunţ. Coloanele vor fi numerotate începând de la 1, iar dacă există mai multe soluţii va fi afişată cea mai mică în ordine lexicografică: perechea *(k, l)* va fi afişată înaintea perechii *(k’, l’)* dacă $k < k’$ sau dacă $k = k’$ şi $l < l’$ *(adică E < N < S < V)*.

h2. Restricţii

* Matricea minimală a unei case are maximum 100000 elemente.

* Matricea minimală a unei case are maximum $100000$ elemente.

h2. Exemplu