0565 - Acoperire

Sursă: [1]

Cerință

Gigel deține un teren de formă dreptunghiulară, împărțite în n•m sectoare, dispuse pe n linii și m coloane. În anumite sectoare sunt instalate camere de luat vederi. Fiecare cameră acoperă anumite sectoare ale terenului, pe diagonală și are o anumită putere k reprezentând numărul de sectoare pe care le acoperă pe fiecare din cele 4 direcții, inclusiv sectorul în care se află camera. Determinați câte sectoare ale terenului nu sunt acoperite de nici o cameră.

Date de intrare

Programul citește de la tastatură numerele n m k, reprezentând dimensiunile terenului și numărul de camere, apoi k triplete i j p, reprezentând coordonatele fiecărei camere șî puterea ei.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Programul va afișa pe ecran numărul C, reprezentând numărul de sectoare neacoperite. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricții și precizări

• 1 ≤ n , m ≤ 1000
• 1 ≤ p ≤ 1000
• 1 ≤ j ≤ m
• 1 ≤ p ≤ min(n,m)
• o cameră poate acoperi un sector în care se află o altă cameră

Exemple

Exemplu 1

Date de intrare

1 7 2

4 2 3

4 5 4

Date de ieșire

16

Rezolvare

<syntaxhighlight lang="python" line="1"> def citeste_n_m_k():

   while True:
       try:
           n = int(input("Introduceti numarul n: "))
           m = int(input("Introduceti numarul m: "))
           k = int(input("Introduceti numarul k: "))
           if 1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= k <= 1000:
               print("Datele sunt corecte.")
               return n,m,k
           else:
               print("Datele nu sunt conform restrictiilor impuse.")
       except ValueError:
           print("Trebuie introduse doar numere intregi.")

def citeste_triplet(n, m):

   valori = []
   for i in range(n):
       while True:
           try:
               i,j,p = map(int, input("Introduceti tripletul de valori separate prin spatiu: ").split())
               if 1 <= i <= n and 1 <= j <= m and 1 <= p <= min(n,m):
                   print("Datele sunt corecte.")
                   valori.append((i,j,p))
                   break
               else:
                   print("Datele nu sunt conform restrictiilor impuse.")
           except ValueError:
               print("Trebuie introduse doar valori numerice.")

   return valori

def Acoperire(valori, n, m):

   a = [[-1 for j in range(m+1)] for i in range(n+1)]
   cnt = 0
   for i,j,p in valori:
       a[i][j] = p
       for l in range(1, p+1):
           if i + l <= n and j + l <= m:
               a[i+l][j+l] = p
           if i + l <= n and j - l > 0:
               a[i+l][j-l] = p
           if i - l > 0 and j + l <= m:
               a[i-l][j+l] = p
           if i - l > 0 and j - l > 0:
               a[i-l][j-l] = p
   for i in range(1, n+1):
       for j in range(1, m+1):
           if a[i][j] == -1:
               cnt += 1
   return cnt

if _name_ == '_main_':

   n, m, k = citeste_n_m_k()
   valori = citeste_triplet(k, m)
   cnt = Acoperire(valori, n, m)
   print("Numarul de sectoare neacoperite este:", cnt)

</syntaxhighlight>

Explicatie

Acest cod este o implementare a unui algoritm care calculează numărul de sectoare neacoperite de o matrice dată, folosind informații despre un set de triplete formate din trei valori întregi (i, j, p) care semnifică: linia i, coloana j și raza de acoperire p a unui sector circular centrare în (i,j).

Funcția citeste_n_m_k() citește de la tastatură valorile pentru n, m și k, reprezentând dimensiunile matricei și numărul de triplete, iar apoi verifică dacă valorile sunt conforme cu restricțiile impuse: n, m și k trebuie să fie între 1 și 1000. Dacă valorile sunt corecte, funcția le returnează.

Funcția citeste_triplet(n, m) primește numărul de triplete k și dimensiunea m și citește de la tastatură k triplete (i, j, p), reprezentând coordonatele centrului sectorului circular și raza de acoperire a acestuia. După citire, funcția verifică dacă tripletele sunt conforme cu restricțiile impuse: i și j trebuie să fie între 1 și n și respectiv între 1 și m, iar p trebuie să fie între 1 și min(n,m). Tripletele valide sunt adăugate la o listă de valori și apoi returnate.

Funcția Acoperire(valori, n, m) primește lista de valori citite anterior și dimensiunile matricei și calculează numărul de sectoare neacoperite. Înainte de a începe procesul de acoperire, se creează o matrice a de dimensiuni n+1 x m+1, inițializată cu valoarea -1 pentru toate elementele, pentru a putea verifica mai ușor dacă un sector a fost acoperit sau nu. Apoi, pentru fiecare triplet de valori citite, se actualizează matricea a, setând valoarea razei p pentru fiecare element de pe cercul centrat în (i,j). Se actualizează de asemenea și elementele din interiorul cercului, mărind raza de la 1 la p. La final, se numără câte elemente din matricea a au valoarea -1, semnificând sectoarele neacoperite, și se returnează acest număr.

Funcția main() apelează funcțiile citeste_n_m_k(), citeste_triplet(k, m) și Acoperire(valori, n, m) și afișează numărul de sectoare neacoperite.