Editing 3686 - Vaccination

<u>''Cerință''</u>

Echipa V.R.N.C. a dezvoltat un vaccin contra celei mai recente boli. Vaccinul este distribuit mai întâi unei singure persoane, iar mai apoi se împrăștie celor 4 vecini(populația este reprezentată pe o matrice de dimensiunile n și m). Ulterior, fiecare persoana va da vaccinul celor 4 vecini până când o persoană de la marginea matricii este vaccinată, moment în care vaccinul nu mai este dat mai departe.

Vazând succesul acestei metode, V.R.N.C ne dă o matrice în care știm vârsta fiecărei persoane și trebuie să aflăm punctul unde V.R.N.C ar trebui să înceapă distribuția vaccinului astfel încât să maximizăm suma vârstelor oamenilor vaccinați.

<u>''Date de intrare''</u>

Programul citește de la tastatură pe prima linie numerele n și m, iar apoi n linii, fiecare linie conținând m numere separate prin spații, reprezentând vârstele celor n*m cetățeni

<u>''Date de ieșire''</u> 

Programul va afișa pe ecran două valori i și j, locul unde vaccinarea ar trebui să înceapă. Dacă sunt mai multe soluții, trebuie afișată cea mai din stânga-sus poziție.

Restricții și precizări

1 ≤ n, m ≤ 1000

cele n*m numere citite vor fi între 0 și 2147483647

<u>''Exemplu:''</u>

<u>''Intrare''</u>

3 4

1 2 3 4

5 6 7 8

9 10 11 12

<u>''Ieșire''</u>

2 3

<u>''Explicație''</u>

Începând de la celula (2, 3) cu valoarea 7, vaccinul va ajunge și la valorile 3, 6, 8 și 11, suma fiind 35, aceasta fiind suma maximă posibilă obținută.

<u>''Rezolvare''</u>

def get_vecini(matrice, i, j):

    vecini = []

    randuri, coloane = len(matrice), len(matrice[0])

    # Verificăm vecinii de sus, jos, stânga și dreapta și îi adăugăm în lista "vecini"

    if i > 0:

        vecini.append(matrice[i - 1][j])

    if i < randuri - 1:

        vecini.append(matrice[i + 1][j])

    if j > 0:

        vecini.append(matrice[i][j - 1])

    if j < coloane - 1:

        vecini.append(matrice[i][j + 1])

    return vecini

def maximizeaza_distributia_vaccinului(matrice):

    suma_maxima = 0

    start_i, start_j = 0, 0

    randuri, coloane = len(matrice), len(matrice[0])

    # Iterăm prin matrice, excludem marginea superioară și inferioară

    for i in range(1, randuri - 1):

        for j in range(coloane):

            # Calculăm suma vârstei curente și a vecinilor

            suma_curenta = matrice[i][j]

            vecini = get_vecini(matrice, i, j)

            suma_curenta += sum(vecini)

            # Verificăm dacă suma curentă este mai mare decât suma maximă

            if suma_curenta > suma_maxima:

                suma_maxima = suma_curenta

                start_i, start_j = i, j

    return start_i, start_j + 1  # Adăugăm 1 pentru a afișa poziția corectă

<nowiki>#</nowiki> Citire date de intrare

n, m = map(int, input().split())

varste_matrice = [list(map(int, input().split())) for _ in range(n)]

<nowiki>#</nowiki> Calcul și afișare rezultat

start_i, start_j = maximizeaza_distributia_vaccinului(varste_matrice)

print(f"Locul de start pentru vaccinare: ({start_i + 1}, {start_j})")