4058 - Ronti

Cerinţă

La ferma din comuna Iepurești există un teren de forma dreptunghiulară în care fermierii satului au creat mai multe grădini în care au plantat morcovi. Terenul este împărțit în nxm unități (n reprezintă numărul de linii, iar m reprezintă numărul de coloane) numite celule. Morcovii nu sunt plantați uniform astfel încât în celule diferite pot exista numere diferite de morcovi. Grădinile sunt separate între ele prin garduri de diverse forme și lățimi, gardurile ocupând și ele un număr întreg de unități din teren.

Iepurele Ronți vrea să știe în ce grădină să intre pentru a aduna cât mai mulți morcovi dintr-un singur raid asupra terenului și vă cere să-l ajutați și să-i spuneți care este numărul maxim de morcovi pe care îl adună și de unde trebuie să înceapă pentru a aduna acea cantitate. Din celula în care se află, el poate sări maxim k unități, putând astfel să sară peste eventuale garduri dintre grădini. Ronți poate sări doar în direcțiile N, S, E și V.

Date de intrare

Fișierul de intrare ronti.in conține pe prima linie trei numere naturale n, m și k, separate printr-un spațiu, cu semnificația din enunț. Fiecare dintre următoarele n linii conține câte m numere naturale separate prin câte un spațiu. O valoare 0 semnifica faptul că acea unitate face parte dintr-un gard, iar o valoare nenulă reprezintă numărul de morcovi din unitate.

Date de ieșire

Fișierul de ieșire ronti.out va conține pe prima linie doua numere naturale x și y, reprezentând coordonatele unității din care trebuie să pornească Ronți pentru a obține numărul maxim de morcovi, iar pe următoarea linie a fișierului numărul maxim de morcovi obținut în urma raidului.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• Numărul de morcovi din fiecare unitate este mai mic decât 200.000
• Dacă există două drumuri cu același număr maxim de morcovi adunați, se va alege drumul care are poziția de start cea mai mică din punct de vedere lexicografic
• Perechea (i, j) este mai mică în sens lexicografic decât perechea (x, y) dacă i<x sau dacă i=x și j<y

Exemple

Exemplul 1

Intrare

ronti.in

4 8 2 1 2 0 1 1 0 0 10 3 4 0 1 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 0 3 3

Ieșire

ronti.out

1 1 30

Rezolvare

def e_valid(k, i, j, n, m):
    """
    Verifică dacă celula (i, j) se află pe hartă și poate fi atinsă în k pași.
    """
    if i < 0 or i >= n or j < 0 or j >= m:
        return False
    if k < 0:
        return False
    return True


def cauta_maxim(harta, vizitat, k, i, j, n, m):
    """
    Caută celula de pe hartă de la care se poate obține numărul maxim de morcovi într-un raid de cel mult k pași.
    Returnează numărul maxim de morcovi și coordonatele de început ale raidului.
    """
    if not e_valid(k, i, j, n, m) or vizitat[i][j]:
        return 0, (i, j)

    vizitat[i][j] = True
    morcovi = harta[i][j]
    max_morcovi = morcovi
    start = (i, j)

    for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        s, p = cauta_maxim(harta, vizitat, k-1, x, y, n, m)
        if s > max_morcovi:
            max_morcovi = s
            start = p
        elif s == max_morcovi and p < start:
            start = p

    vizitat[i][j] = False
    return morcovi + max_morcovi, start


def rezolva(n, m, k, harta):
    """
    Găsește celula de pe hartă de la care se poate obține numărul maxim de morcovi într-un raid de cel mult k pași.
    Returnează o listă de tuple cu punctele de start și numărul maxim de morcovi.
    """
    maxim = 0
    solutii = []
    vizitat = [[False] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            s, p = cauta_maxim(harta, vizitat, k, i, j, n, m)
            if s > maxim:
                maxim = s
                solutii = [(p, s)]
            elif s == maxim:
                solutii.append((p, s))

    return solutii[0]


def main():
    # citire date de intrare
    with open('ronti.in', 'r') as f:
        n, m, k = map(int, f.readline().split())
        harta = []
        for i in range(n):
            linie = list(map(int, f.readline().split()))
            harta.append(linie)

    # rezolvare
    start, maxim = rezolva(n, m, k, harta)
    print(start)
    print(maxim)

    # scriere date de ieșire
    with open('ronti.out', 'w') as f:
        i, j = start[0], start[1]
        f.write(f"{i+1}  {j+1}\n")
        f.write(f"{maxim}\n")

if __name__ == '__main__':
    main()

Explicație rezolvare

Acest cod are rolul de a rezolva o problemă de tip backtracking. Scopul problemei este de a găsi celula de pe o hartă, din care se pot obține cele mai multe morcovi într-un raid de cel mult k pași.

1. 1 Funcția e_valid verifică dacă o celulă dată este validă, adică se află pe hartă și poate fi atinsă în k pași.

1. 2 Funcția cauta_maxim este funcția principală de backtracking care găsește celula de pe hartă care poate fi atinsă în cel mult k pași și care aduce cele mai multe morcovi. Funcția începe cu celula dată ca argument, adună morcovii din acea celulă și verifică dacă celula dată este vizitată și dacă este validă. Dacă celula este vizitată sau nu este validă, se va întoarce 0 morcovi și coordonatele celulei actuale. Altfel, se va trece la celulele adiacente și se va aduna morcovii. Funcția va întoarce celulele cu cele mai multe morcovi și coordonatele celulei respective.

1. 3 Funcția rezolva este cea care găsește celula cu cele mai multe morcovi și apelează funcția cauta_maxim pentru fiecare celulă de pe hartă. Funcția începe cu cele mai mici coordonate și verifică toate celulele de pe hartă. Dacă se găsește o celulă cu mai mulți morcovi, se actualizează valoarea maximă și se actualizează soluția.

1. 4 Funcția main citește datele de intrare dintr-un fișier, apelează funcția rezolva, afișează celula de start și numărul maxim de morcovi și scrie datele de ieșire într-un fișier.