Într-o grădină botanică zonele în care se găsesc plante aparţinând aceleaşi specii sunt înconjurate de gard viu, de grosime neglijabilă. O specie ocupă o singură zonă. Suprafaţa grădinii, de formă dreptunghiulară, este împărţită în porţiuni de 1x1. Fiecare porţiune poate avea (sau nu) pe fiecare din laturile dinspre V, N, E sau S gard viu.
Cerinţă
Cunoscând planul codificat al grădinii determinaţi:
– numărul speciilor de plante ce se găsesc în grădină;
– suprafaţa maximă ocupată de o singură specie;
– suprafaţă de arie maximă ce se poate obţine prin unirea a două zone, precum şi poziţia porţiunii de gard (de dimensiune 1) prin a cărei îndepărtare se obţine această suprafaţă.
Date de intrare
Fişierul de intrare gradina.in are structura: n m
a11 a12 ... a1m
a21 a22 ... a2m
...
an1 an2 ... anm
unde
n, m - lungimea respectiv lăţimea grădinii exprimate în metri
a11 a12 ... a1m - descriere linia 1 pentru planul grădinii
a21 a22 ... a2m - descriere linia 2 pentru planul grădinii
...
an1 an2 ... anm - descriere linia n pentru planul grădinii
unde aij reprezintă codificările porţiunilor din suprafaţa grădinii, astfel:
- 0 daca nu are gard viu pe nici una din laturile V,N,E,S
- la codificare se adaugă: 1 dacă există gard viu spre V 2 dacă există gard viu spre N 4 dacă există gard viu spre E 8 dacă există gard viu spre S
Date de ieşire
Fişierul de ieşire gradina.out are structura: Ns
Amax
aria lmax cmax dmax
unde
Ns - numărul speciilor de plante Amax - aria maximă aria lmax cmax dmax - aria ce se obţine prin unirea a două zone, linia, coloana şi latura (N, E, S, V) porţiunii de gard ce trebuie eliminată, separate prin câte un spaţiu.
Restricţii
1 <= N, M <= 20
- în cazul în care există mai multe soluţii de obţinere a ariei maxime se va indica cea pentru care numărul liniei zonei eliminate este minim, iar dacă există mai multe soluţii cu numărul de linie minim, cea care are numărul coloanei minim
