Cerința
Se dă o matrice binară (valori 0
și 1
). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1
.
Date de intrare
Fișierul de intrare lsq.in
conține pe prima linie numerele N
și M
, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N
linii, pe fiecare câte M
valori 0
sau 1
, neseparate prin niciun spațiu, reprezentând elementele matricei..
Date de ieșire
Fișierul de ieșire lsq.out
va conține pe prima linie numărul L
, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1
pe marginea sa.
Restricții și precizări
1 ≤ N, M ≤ 1000
- Se consideră pătrat și cel de latură
1
(conține doar un element).
Exemplu:
lsq.in
7 7 0000000 0111100 0101111 0100101 0111111 0000011 0000011
lsq.out
4
Explicație
0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 0 1 1 1 1
0 1 0 0 1 0 1
0 1 1 1 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 1 1