Reputation: 444
The problem that I am stuck is that a person needs to go from the top-left of a 2-D array containing integers to the bottom-right position, gaining maximum possible score, either moving down or right. However, if a position A[i][j] is less than 0, then the person can't move past it and a amount equal to this negative value will be subtracted from the score every time the person visits a neighborhood of such position. I know that its a standard DP problem and that I could make a array T[][] with T[i][j] representing the maximum score till position i,j from 0,0. However, I am unable to come up with any proper implementation of the condition that person should not move past the cell marked with a negative integer. For example, if rows=2;column=3; and
A= | 0 -4 8 |
| 1 1 0 |
then i want the answer to be -6, i.e. the matrix T should be
T=| 0 -4 X |
| -3 -6 -6 |
Upvotes: 3
Views: 1756
Reputation: 9930
I was following the same train of thought as suggested in the answer by dwrd, so I tried implementing it in Python. There are a few things to consider that I hadn't thought initially but I think I finally got it working.
Here's the code, it surely needs some polishing up, but it's a start:
def get_score(M, i, j):
"Get the final score for position [i, j.]"
score = 0
if M[i][j] < 0:
score = -float('inf')
else:
score = M[i][j]
score = score + penalty(M, i - 1, j - 1)
score = score + penalty(M, i - 1, j + 1)
score = score + penalty(M, i + 1, j - 1)
score = score + penalty(M, i + 1, j + 1)
score = score + penalty(M, i - 1, j)
score = score + penalty(M, i, j - 1)
score = score + penalty(M, i + 1, j)
score = score + penalty(M, i, j + 1)
return score
def penalty(M, i, j):
"Calculate the penalty for position [i, j] if any."
if i >= 0 and i < len(M) and j >= 0 and j < len(M[0]):
return (0 if M[i][j] > 0 else M[i][j])
return 0
def calc_scores(M):
"Calculate the scores matrix T."
w = len(M[0])
h = len(M)
T = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
for j in range(w):
T[i][j] = get_score(M, i, j)
T[0][0] = 0
T[h - 1][w - 1] = 0
return T
def calc_max_score(A, T):
"Calculate max score."
w = len(A[0])
h = len(A)
S = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
for i in range(1, h + 1):
for j in range(1, w + 1):
S[i][j] = max(S[i - 1][j], S[i][j - 1]) + T[i - 1][j - 1]
# These are for the cases where the road-block
# is in the frontier
if A[i - 1][j - 2] < 0 and i == 1:
S[i][j] = -float('inf')
if A[i - 2][j - 1] < 0 and j == 1:
S[i][j] = -float('inf')
return S
def print_matrix(M):
for r in M:
print r
A = [[0, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)
print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'
A = [[0, 1, 1], [4, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)
print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'
You get the following output:
----------
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -inf, -inf]
[0, -3, -6, -6]
----------
----------
[0, -3, -3]
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -3, -3]
[0, 0, -inf, 1]
[0, -3, -6, 1]
----------
Upvotes: 1
Reputation: 1689
The idea is emulating inability to move into negative cell with negative infinity result that will be never selected as maximum. Pseudocode:
int negativePart(int i, int j)
{
if (i < 0 || j < 0)
return 0;
return A[i, j] < 0 ? A[i, j] : 0;
}
int neighborInfluence(int i, int j)
{
if (int == Height -1 && j == Width - 1)
return 0;
return negativePart(i-1, j-1) + negativePart(i-1,j)+// so on, do not think about negative indexes because it was already processed in negativePart method
}
int scoreOf(int i, int j)
{
return A[i,j] < 0 ? <NegativeInfinity> : A[i,j] + neighborInfluence(i,j);
}
//.......
T[0,0] = A[0,0];
for (int i = 1; i < heigth; ++i)
{
T[i, j] = T[i - 1, 0] + scoreOf(i, 0);
}
for (int i = 1; i < width; ++i)
{
T[0, i] = T[0, i - 1] + scoreOf(0, i);
}
for (int i = 1; i < heigth; ++i)
{
for (int j = 1; j < width; ++j)
{
T[i, j] = max(T[i - 1, j], T[i, j - 1]) + scoreOf(i, j);
}
}
Upvotes: 1