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

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)

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.