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.