Harta digitală a câmpului de luptă este memorată într-un tablou bidimensional cu N linii, M coloane şi elemente din mulţimea {0,1}. Valoarea 0 reprezintă o poziţie liberă, iar valoarea 1 reprezintă o poziţie ocupată de un obstacol. În fiecare element aflat pe conturul tabloului, adică pe prima linie, prima coloana, ultima linie şi ultima coloană, se află obiective inamice. Pe conturul tabloului se găsesc numai elemente nule.
În interiorul tabloului (elementele care nu se află pe contur), într-o poziţie liberă, trebuie plasat un soldat. Scopul său este să anihileze cât mai multe obiective inamice. Din păcate, el deţine o armă laser cu care poate executa doar un singur atac. La lansarea atacului, se trimit 4 raze, câte una în fiecare dintre cele 4 direcţii diagonale. O rază poate merge până la întâlnirea unui obstacol (în acest caz se opreşte şi nu va avea nici un efect) sau până ajunge pe contur (în acest caz distruge obiectivul inamic respectiv).

Cerinţă

Scrieţi un program care determină numărul maxim de obiective inamice, notat cu K, ce pot fi distruse în urma unui atac, precum şi numărul poziţiilor în care putem plasa soldatul pentru a distruge K obiective inamice.

Date de intrare

Fişierul de intrare raze.in conţine pe prima linie se găseşte numărul natural T, reprezentând numărul seturilor de date de intrare. Pentru fiecare set de date de intrare în fişierul de intrare pe prima linie a setului se află numerele naturale N şi M, separate printr-un spaţiu, reprezentând numărul liniilor, respectiv numărul coloanelor tabloului; pe următoarele N linii ale setului de date se află câte M numere naturale din mulţimea {0,1}, separate prin câte un spaţiu, reprezentând forma digitală a hărţii câmpului de luptă.

Date de ieşire

Fişierul de ieşire raze.out va conţine T linii, corespunzătoare celor T seturi de date de intrare. Pe fiecare linie se vor tipări două numere naturale K şi P, separate printr-un spaţiu, reprezentând numărul maxim de obiective inamice distruse în atac, respectiv numărul poziţiilor din care se pot distruge K obiective inamice.

Restricţii

1≤ T ≤ 80
3≤ N, M ≤ 135
Se garantează că există cel puţin un obiectiv inamic ce poate fi anihilat pentru fiecare set de date de intrare.

Exemple

raze.in	raze.out	Explicaţii
2 4 6 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 7 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	4 1 3 2	În fişier se găsesc două seturi de date de intrare. În primul set de date se pot anihila maximum 4 obiective inamice, poziţionând soldatul în linia 2 şi coloana 2. În al doilea set de date se pot anihila maximum 3 obiective inamice, poziţionând soldatul în elementul de pe linia 3 şi coloana 2 sau în elementul din linia 3 şi coloana 6.

autor: Prof. Marius Nicoli

propunător: Prof. Emanuela Cerchez

Liceul de Informatică ″Grigore Moisil″

emanuela.cerchez@gmail.com