w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
minimum cost path through a cost matrix with positive and negative cost

Let's say that H[i, j] is the minimum health the player needs when starting from square (i, j). We are interested in H[1, 1], which is the minimum health needed from the starting square.

I assume that all values in the cost matrix M are integers. Therefore, the smallest positive health is 1.

The required health before stepping on the last square is easy: if the value in that square is positive we need 1, otherwise we need at least more than what gets subtracted:

H[m, n] = max(1 - M[m, n], 1)

The other easy ones are the edges of the matrix: M[m, i] and M[j, n] for arbitrary i and j. If the current value is negative we have to increase the required health buffer, otherwise we can decrease it (but never further than 1):

H[m, i] = max(H[m, i+1] - M[m, i], 1)
H[j, n] = max(H[j+1, n] - M[j, n], 1)

In the center of the matrix we have both choices (going right and down), so we take the minimum of those alternatives:

H[i, j] = min(max(H[i, j+1] - M[i, j], 1),
              max(H[i+1, j] - M[i, j], 1))

That's about it! Converting this to code is straightforward (assuming M, m, and n are given and M is 1-based):

int[] H = new int[m, n];

H[m, n] = max(1 - M[m, n], 1);

// remember to loop backwards
for (int i = m-1; i >= 1; i--)
    H[m, i] = max(H[m, i+1] - M[m, i], 1);
for (int j = n-1; j >= 1; j--)
    H[j, n] = max(H[j+1, n] - M[j, n], 1);

// again, loop backwards
for (int i = m-1; i >= 1; i--)
    for (int j = n-1; j >= 1; j--)
        H[i, j] = min(max(H[i, j+1] - M[i, j], 1),
                      max(H[i+1, j] - M[i, j], 1));

return H[1, 1];




© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.