submatrix

Fie A o matrice cu n linii (numerotate de la 1 la n) si m coloane (numerotate de la 1 la m) cu componente din multimea {0, 1}.
Se numeste submatrice de coordonate (L1, C1, L2, C2) o zona dreptunghiulara din matrice care are coltul stanga-sus pe linia L1, coloana C1 si coltul dreapta-jos pe linia L2, coloana C2 (L1<=L2, C1<=C2).
Dimensiunea unei submatrice este egal cu numarul de elemente din submatricea respectiva.

Cerinta

Scrieti un program care sa determine o submatrice de dimensiune maxima formata numai din 1.

Date de intrare

Fisierul de intrare submatrix.in contine pe prima linie numerele naturale n si m, separate printr-un spatiu, cu semnificatia din enunt.
Pe fiecare dintre urmatoarele n linii se afla cate m cifre din multimea {0, 1}. Cifrele de pe aceeasi linie nu sunt separate prin spatii.

Date de iesire

Fisierul de iesire submatrix.out va contine pe prima linie dimensiunea submatricei determinate (maxima posibil). Pe cea de a doua linie vor fi scrise 4 numere naturale separate prin cate un spatiu, L1 C1 L2 C2, unde (L1,C1) reprezinta linia si coloana pe care se afla coltul stanga-sus al submatricei determinate, iar (L2,C2) reprezinta linia si coloana pe care se afla coltul dreapta-jos al submatricei. Daca exista mai multe solutii, se va afisa o solutie pentru care linia coltului stanga-sus este minima. Daca si in acest caz exista mai multe solutii, se alege cea pentru care coloana coltului stanga-sus este minima. In sfarsit, daca si acum exista mai multe solutii, va fi scrisa cea pentru care linia coltului dreapta-jos este minima.

Restrictii

1 <= n, m <= 100

Exemple

Timp maxim de executie/test: 0.5 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com