Considerăm o matrice pătratică având N linii şi N coloane care memorează numai valori 0 şi 1. Matricea suferă transformări în mai mulţi paşi. La fiecare pas, toate componentele din matrice marcate cu 0 se vor transforma în 1 dacă au cel puţin 3 vecini (pe linie, coloană şi diagonale) marcate cu 1. Procesul de transformare se repetă la fiecare pas, până când matricea are peste tot valoarea 1 sau până când nu mai poate surveni nicio transformare. Mai jos este prezentată o matrice şi modul în care se efectuează transformările în 7 paşi.

00000 01000 10100 01000 00000	00000 01000 11100 01000 00000	00000 11100 11100 11100 00000	01000 11100 11110 11100 01000	11100 11110 11110 11110 11100	11110 11110 11111 11110 11110	11110 11111 11111 11111 11110	11111 11111 11111 11111 11111
Iniţial	Pas 1	Pas 2	Pas 3	Pas 4	Pas 5	Pas 6	Pas 7

Cerinţă

Să se determine numărul de paşi necesari ca matricea să aibă peste tot valoarea 1, sau până când nu mai are loc nicio transformare.

Date de intrare

Fişierul de intrare fillmat.in conţine pe prima linie un număr natural N reprezentând dimensiunea matricei. Pe următoarele N linii se găsesc exact N caractere 0 şi 1 reprezentând câte o linie din matrice. Elementele de pe linii nu sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire fillmat.out va conţine un singur număr natural reprezentând numărul de paşi necesari pentru ca matricea să conţină peste tot valoarea 1, sau până când nu mai are loc nicio transformare.

Restricţii

• 3 <= N <= 300
• Zonele vecine poziţiei (i, j) sunt: (i-1,j-1), (i-1,j), (i-1,j+1), (i,j+1), (i,j-1), (i+1,j-1), (i+1,j), (i+1,j+1).

Exemplu

fillmat.in	fillmat.out
5 00000 01000 10100 01000 00000	7

prof. Dan Pracsiu

Grupul Şcolar "Ştefan Procopiu" Vaslui

dpracsiu@yahoo.com