Editing 1189 - Lenes

Leneşul este un animal foarte leneş. El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice  de dimensiuni <code>M×N</code> cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de <code>k1</code>, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face <code>k2</code> popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.

= Cerințe =
Cunoscând dimensiunile <code>M</code>, <code>N</code> ale terenului, numărul de popasuri <code>k1</code>, <code>k2</code> și efortul pentru traversarea fiecărei zone a terenului, să se determine:

# Efortul minim de parcurgere a terenului de la Nord la Sud, folosind <code>k1</code> popasuri.
# Efortul minim de parcurgere a terenului de la Nord la Sud și înapoi de la Sud la Nord, folosind <code>k1</code> popasuri la deplasarea Nord – Sud, respectiv <code>k2</code> popasuri la deplasarea Sud – Nord.

= Date de intrare =
Fișierul de intrare <code>lenes.in</code> conține:

* Pe prima linie un număr natural <code>p</code> reprezentând cerința de rezolvare. Pentru toate testele de intrare numărul <code>p</code> poate avea doar valoarea <code>1</code> sau <code>2</code>.
* Pe linia a doua sunt <code>4</code> numere naturale <code>M</code>, <code>N</code>, <code>k1</code>, <code>k2</code>, separate prin câte un spațiu cu semnificaţia de mai sus.
* Pe următoarele <code>M</code> linii se găsesc câte <code>N</code> numere naturale separate prin câte un spațiu, reprezentând eforturile de traversare a fiecărei zone a terenului.

= Date de ieșire =
Dacă valoarea lui <code>p</code> este <code>1</code>, se va rezolva numai cerința 1. În acest caz fişierul <code>lenes.out</code> va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date de la Nord la Sud.

Dacă valoarea lui <code>p</code> este <code>2</code>, se va rezolva numai cerința 2. În acest caz fişierul <code>lenes.out</code> va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date în ambele sensuri de la Nord la Sud și de la Sud la Nord.

= Restricții și precizări =

* <code>3 ≤ M, N ≤ 500</code>
* <code>0 ≤ k1, k2 ≤ M</code>
* Valorile din matrice sunt numere naturale din intervalul <code>[1, 1000]</code>.
* Leneșul poate să facă popasuri pe aceeaşi linie în ambele celule din stânga şi din dreapta coloanei parcurse.
* Deplasarea între ultima zonă a drumului parcurs de la Nord la Sud şi prima zonă a drumului parcurs de la Sud la Nord la întoarcere se face cu efort <code>0</code>.

= Exemplul 1 =
<code>lenes.in</code>
 1
 4 7 2 3
 99 1 33 9 2 4 7
 99 1 44 8 1 2 3
 98 1 55 8 2 3 2
 97 1 66 4 3 2 1
<code>lenes.out</code>
 12

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

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

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

= Exemplul 2 =
<code>lenes.in</code>
 2
 4 7 3 2
 99 1 33 9 2 4 7
 99 1 44 8 1 2 3
 98 1 55 8 2 2 2
 97 1 66 4 3 2 1
<code>lenes.out</code>
 35

= 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>