Fişierul intrare/ieşire:spirala3.in, spirala3.outSursăAlgoritmiada 2012, Runda 4
AutorCosmin Silvestru NegruseriAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/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.inspirala3.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?