0840 - Croco

Cerința

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

Să se plaseze pe fiecare zonă cu uscat un crocodil sau un elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate.

Date de intrare

Fișierul de intrare croco.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 croco.out va conține n linii, fiecare cu câte m caractere din mulțimea {A, C, E}, separate prin câte un spațiu, după cum în zona corespunzătoare a lacului este apa, crocodil sau elefant.

Restricții și precizări

• 1 ≤ n , m ≤ 100
• se acceptă orice soluție corectă

Exemplu

Exemplu1

Intrare:

croco.in

3 5

1 1 1 0 1

1 1 0 1 1

0 1 1 0 1

Iesire:

croco.out

C E C A C

E C A C E

A E C A C

Rezolvare

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

def valideaza_intrare(n, m, matrice):

   if not (1 <= n <= 100 and 1 <= m <= 100):
       return False
   for i in range(n):
       if len(matrice[i]) != m:
           return False
       for j in range(m):
           if matrice[i][j] not in ['0', '1']:
               return False
   return True

def rezolva(n, m, matrice):

   animale = ['C', 'E']
   animal_curent = 0
   rezultat = [[ for _ in range(m)] for _ in range(n)]

   for i in range(n):
       for j in range(m):
           if matrice[i][j] == '0':
               rezultat[i][j] = 'A'
           else:
               for animal in animale:
                   if (i > 0 and rezultat[i-1][j] == animal) or \
                      (j > 0 and rezultat[i][j-1] == animal) or \
                      (i < n-1 and rezultat[i+1][j] == animal) or \
                      (j < m-1 and rezultat[i][j+1] == animal):
                       continue
                   else:
                       rezultat[i][j] = animal
                       break
               else:
                   animal_curent = (animal_curent + 1) % 2
                   rezultat[i][j] = animale[animal_curent]

   return rezultat

def afiseaza_rezultat(rezultat):

   with open('croco.out', 'w') as f:
       for row in rezultat:
           f.write(' '.join(row) + '\n')

if __name__ == '__main__':

   with open('croco.in', 'r') as f:
       n, m = map(int, f.readline().strip().split())
       matrice = [list(f.readline().strip().split()) for _ in range(n)]

   if not valideaza_intrare(n, m, matrice):
       print('Date invalide!')
   else:
       rezultat = rezolva(n, m, matrice)
       afiseaza_rezultat(rezultat)

</syntaxhighlight>

Explicații

În prima parte a codului, avem funcția validate_input(n, m, matrix) care primește dimensiunile matricei și matricea însăși și verifică dacă intrările sunt valide. Această funcție verifică dacă n și m sunt între 1 și 100, iar matricea este o matrice binară de dimensiune n x m. Dacă intrările sunt invalide, funcția returnează False, altfel returnează True.

1. 1 În funcția solve(n, m, matrix), începem prin a defini lista animals care conține animalele pe care le putem atribui unei celule: C și E. Variabila current_animal este folosită pentru a urmări ultima animală atribuită și pentru a alterna între cele două animale. Lista rezultat result este inițializată cu caracterele goale.

1. 2 Următorul pas este de a parcurge matricea, de la stânga la dreapta și de sus în jos. Dacă întâlnim o celulă cu valoarea 0, atribuim caracterul A în acea celulă. În caz contrar, verificăm celulele din jurul acelei celule pentru a vedea dacă am mai atribuit deja același animal. Dacă am făcut-o, trecem la următoarea celulă. Dacă nu, alegem animalul opus ultimului animal atribuit și îl atribuim acelei celule. Acest lucru se face pentru a asigura faptul că animalele sunt atribuite alternativ.

Dacă nu se poate atribui nici unul dintre cele două animale, schimbăm animalul și încercăm din nou. Dacă după schimbarea animalului nu putem atribui niciunul dintre cele două animale, înseamnă că am epuizat ambele opțiuni și atribuim celula cu caracterul A.

1. 3 În final, funcția solve() returnează matricea rezultat result.

1. 4 Funcția print_result(result) primește matricea rezultat și o afișează pe ecran într-un format ușor de citit, unde fiecare linie a matricei este afișată pe o linie separată, iar fiecare element dintr-o linie este separat prin un singur spațiu.

1. 5 În blocul if __name__ == '__main__':, citim datele de intrare din fișierul "croco.in" și le verificăm folosind funcția validate_input(). Dacă datele sunt valide, apelăm funcția solve() pentru a obține matricea rezultat și apoi afișăm matricea rezultat folosind funcția print_result(). În loc să afișăm matricea pe ecran, o scriem în fișierul "croco.out".