0844 - Croco1

Cerința

Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă.

Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare.

Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel încât numărul de crocodili să fie cât mai mare.

Date de intrare

ișierul de intrare croco1.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau 1, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire croco1.out va conține pe prima linie numerele C E, reprezentând numărul de crocodili, respectiv numărul de elefanți care pot fi plasați în condițiile precizate, astfel încât numărul de crocodili să fie cât mai mare.

Restricții și precizări

*≤ n , m ≤ 100

Exemplu

Exemplu1

Intrare:

croco1.in

3 5

0 0 0 1 0

0 0 1 0 0

1 0 0 1 0

Iesire:

croco1.out

7 4

Rezolvare

<syntaxhighlight lang="python" line="1">

def valideaza_matrice(matrice):

   for linie in matrice:
       if len(linie) != len(matrice[0]):
           return False
       for element in linie:
           if element != 0 and element != 1:
               return False
   return True

def rezolva_crocodili(matrice):

   nr_crocodili = 0
   nr_elefanti = 0
   directii = [(0, -1), (-1, 0), (0, 1), (1, 0)]
   for i in range(len(matrice)):
       for j in range(len(matrice[0])):
           if matrice[i][j] == 0:
               poate_fi_croc = True
               for dx, dy in directii:
                   x, y = i + dx, j + dy
                   if 0 <= x < len(matrice) and 0 <= y < len(matrice[0]):
                       if matrice[x][y] == 2:
                           poate_fi_croc = False
                           break
               if poate_fi_croc:
                   matrice[i][j] = 2
                   nr_crocodili += 1
   nr_elefanti = sum(linie.count(0) for linie in matrice)
   return nr_crocodili, nr_elefanti

def main():

   with open("croco1.in") as f:
       n, m = map(int, f.readline().split())
       matrice = [list(map(int, f.readline().split())) for _ in range(n)]
   if not valideaza_matrice(matrice):
       print("Matricea data nu este valida.")
       return
   nr_crocodili, nr_elefanti = rezolva_crocodili(matrice)
   with open("croco1.out", "w") as f:
       f.write(f"{nr_crocodili} {nr_elefanti}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicații

1. 1 Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1.
2. 2 Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice.

1. 3 Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire.