3686 - Vaccination

Cerința

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.

Date de intrare

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

Date de ieșire

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

Exemplu:

Intrare

3 4

1 2 3 4

5 6 7 8

9 10 11 12

Ieșire

2 3

Explicație

Î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ă.

Rezolvare

def get_vecini(matrice, i, j):

    vecini = []

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

    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])

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

        for j in range(coloane):

            suma_curenta = matrice[i][j]

            vecini = get_vecini(matrice, i, j)

            suma_curenta += sum(vecini)

            if suma_curenta > suma_maxima:

                suma_maxima = suma_curenta

                start_i, start_j = i, j

    return start_i, start_j + 1  

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

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


start_i, start_j = maximizeaza_distributia_vaccinului(varste_matrice)

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