Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Fillmat

Adăugată de :
sorynsoo
Sursă :
XOR2011
Autor :
-
Grupă :
Medie
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
1200 ms
Limită memorie :
65536 kbytes

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ţa

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 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 iesire

Fişierul de iesire 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 şi precizări:

  • 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)

 

Exemple

  Date de intrare

  Date de iesire

  Date de intrare

  Date de iesire

  5

  00000

  01000

  10100

  01000

  00000

  7  

  5

  01000

  11000

  00000

  00000

  00000

  1


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !