Question

3. You are in a rectangular maze organized in the form of M x N cells/locations. You are starting at the upper left corner (grid location: (1, 1)) and you want to go to the lower right corner (grid location: (M, N)). From any location, you can move either to the right or to the bottom, or go diagonal. I.e., from (i,j) you can move to (i, j + 1) or (i + 1,j) or to (i+1, 3+1). Cost of moving right or down is 2, while the cost of moving diagonally is 3. The grid has several cells that contain diamonds of whose value lies between 1 and 10. I.e, if you land in such cells you gain an amount that is equal to the value of the diamond in the cell.

Answer 1

This problem can be solved by dynamic programming algorithm where if P[i][j] is the maximum profit achievable when reaching from (1,1) to (i,j) .

Then the dynamic programming recurrence relation for computing P[i+1][j+1] will be given by

P[i+1][j+1] = max(P[i+1][j] -2, P[i][j+1] -2 , P[i][j] - 3) + Value[i+1][j+1]

Here Value[i][j] will be earning associated with grid [i][j].

Above dynamic programming recurrence check maximum earning when [i+1][j+1] entered either from [i][j] with cost 3, [i][j+1] or from [i+1][j] with cost 2.

Let's formally write the algorithm .

ALGORITHM()

1. P[1][1]= Value [1][1] //base case

2. For i = 2 to M

3.......P[i][1] = P[i-1][1] + Value[i][1] - 2 //only one way here

4. For j = 2 to N

5.......P[1][j] = P[1][j-1] + Value[1][j]-2 //only one way here

6. For i = 2 to M

7.........For j = 2 to N

8...............P[i][j] = max(P[i-1][j]-2, P[i][j-1]-2, P[i-1][j-1]-3) + Value[i][j]

9. Return P[M][N] //since this is the final solution calculated

Time complexity O(MN).

Please comment for any clarification.