Editing 1189 - Lenes (section)

= Explicație =
<code>p = 2</code>

Leneșul traversează terenul de la Nord la Sud pe coloana a <code>7</code>-a cu popasuri în zonele <code>(3, 6)</code>, <code>(1, 6)</code>, <code>(4, 6)</code>, iar de la Sud la Nord pe coloana a <code>5</code> – a, cu popas în zonele <code>(4, 4)</code> și <code>(2, 6)</code>.

'''Atenție! Pentru acest test se rezolvă doar cerința 2.'''

<syntaxhighlight lang="python" line="1">
import numpy as np

def min_effort_nord_sud(matrix, k1):
    M, N = len(matrix), len(matrix[0])
    inf = float('inf')
    
    # dp[c][r][p]: efort minim pentru a ajunge la (c, r) cu p popasuri rămase
    dp = np.full((M, N, k1 + 1), inf)
    
    # Inițializare
    for r in range(N):
        dp[0][r][k1] = matrix[0][r]
    
    for c in range(1, M):
        for r in range(N):
            for p in range(k1 + 1):
                # Deplasare pe coloana curentă
                if dp[c-1][r][p] < inf:
                    dp[c][r][p] = min(dp[c][r][p], dp[c-1][r][p] + matrix[c][r])
                
                # Popasuri (stânga/dreapta)
                if r > 0 and p > 0:
                    dp[c][r][p-1] = min(dp[c][r][p-1], dp[c-1][r-1][p] + matrix[c][r])
                if r < N - 1 and p > 0:
                    dp[c][r][p-1] = min(dp[c][r][p-1], dp[c-1][r+1][p] + matrix[c][r])
    
    return min(dp[M-1][r][0] for r in range(N))

def min_effort_nord_sud_sud_nord(matrix, k1, k2):
    M, N = len(matrix), len(matrix[0])
    inf = float('inf')
    
    # Minim efort Nord-Sud
    min_effort_nord_sud_val = min_effort_nord_sud(matrix, k1)
    
    # Inversăm matricea pentru Sud-Nord
    matrix_reversed = matrix[::-1]
    
    # Minim efort Sud-Nord
    min_effort_sud_nord_val = min_effort_nord_sud(matrix_reversed, k2)
    
    return min_effort_nord_sud_val + min_effort_sud_nord_val

# Exemple de utilizare
M, N = 4, 5
k1 = 2
k2 = 1
matrix = [
    [2, 4, 1, 8, 3],
    [6, 3, 2, 5, 1],
    [5, 2, 6, 7, 9],
    [8, 4, 2, 1, 5]
]

# Efort minim pentru traversarea Nord-Sud
effort_nord_sud = min_effort_nord_sud(matrix, k1)
print(f"Efort minim pentru traversarea Nord-Sud: {effort_nord_sud}")

# Efort minim pentru traversarea Nord-Sud și Sud-Nord
effort_nord_sud_sud_nord = min_effort_nord_sud_sud_nord(matrix, k1, k2)
print(f"Efort minim pentru traversarea Nord-Sud și Sud-Nord: {effort_nord_sud_sud_nord}")
</syntaxhighlight>