Revizia anterioară Revizia următoare
| 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.
- Semidreapta formata din ultimul element si el sa nu intersecteze vreun alt element care face parte deja din spirala.
Date de intrare
Fişierul de intrare spirala3.in va contine pe prima linie doua numere naturale N si M cu semnificatia din enunt.
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 (1,1) -> (1,2) -> (1,3) -> (1,4) -> (1,5) -> (2,5) -> (3,5) -> (3,4) -> (3,3) -> (3,2) -> (2,2).
Pentru al doilea exemplu, drumul de lungime maxima apare pe pozitiile (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) -> (3,4) -> (3,5) -> (2,5) -> (2,4).
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).
