Editing 4058 - Ronti (section)

==Rezolvare==
<syntaxhighlight lang="python" line="1">
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()
</syntaxhighlight>