| Fişierul intrare/ieşire: | spirala3.in, spirala3.out | Sursă | Algoritmiada 2012, Runda 4 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 66048 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Spirala3
Mescheriakov are o matrice binara de dimenisune NxM. El vrea sa aleaga un set de elemente care sa formeze o spirala astfel:
- Initial Mescheriakov isi fixeaza un sens de parcurgere a spiralei (trigonometric sau orar).
- Apoi isi alege un element al matricei pe care il considera punctul de plecare al spiralei.
- In continuare Mescheriakov poate sa extinda spirala adaugand un element nou care sa indeplineasca urmatoarele conditii:
- Sa nu faca parte deja din spirala.
- Sa fie adiacent cu ultimul element adaugat inaintea sa(pe una din cele 4 directii sus, jos, stanga sau dreapta).
- Semidreapta formata din ultimul element si el sa nu intersecteze vreun alt element care face parte deja din spirala.
- Daca directia de deplasare se schimba atunci ea trebuie sa respecte sensul ales initial.
Ajutati-l pe Mescheriakov sa gaseasca spirala de lungime maxima care contine doar elemente de 0!
Date de intrare
Fişierul de intrare spirala3.in va contine pe prima linie doua numere naturale N si M cu semnificatia din enunt. Pe urmatoarele N linii se vor afla cate M numere din multimea {0, 1} reprezentand matricea binara.
Date de ieşire
În fişierul de ieşire spirala3.out trebuie sa afisati lungimea maxima a unei spirale de 0.
Restricţii
- 1 ≤ N,M ≤ 50
Exemplu
| spirala3.in | spirala3.out |
|---|---|
| 3 5 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 | 11 |
| 3 5 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 | 9 |
| 3 5 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 | 5 |
Explicaţie
In primul exemplu, spirala este data de pozitiile (2,2) -> (3,2) -> (3,3) -> (3,4) -> (3,5) -> (2,5) -> (1,5) -> (1,4) -> (1,3) -> (1,2) -> (1,1).
Pentru al doilea exemplu, drumul de lungime maxima apare pe pozitiile (2,4) -> (2,5) -> (3,5) -> (3,4) -> (3,3) -> (3,2) -> (3,1) -> (2,1) -> (1, 1)
Al treilea exemplu contine doua spirale de lungime maxima, prima de la pozitia (1,1) la pozitia (3,3), si a doua de la pozitia (1,3) la pozitia (5,5).
