CODEWITHSUNDEEP
algorithmgraphdynamic-programming
user3306991
user3306991

Reputation: 145

Optimal Movement in grid

There is a maze of size N*M, consisting of unit blocks. At the start Alice has K percentage of energy. Now Alice start from 1 st row and move towards N th row. From the present block she can move to a block in the next row, which is either on right or on left side of the present block. On moving to a block in i th row j th column, her energy will reduce by C(i,j) percent if C(i,j) is greater then 0, else it will be recharged by C(i,j) percent.

For Example if she has 50 percent of energy, on moving to block with C(i,j) = 15, she will have 35 ( 50 -15 ) percent of the it remaining.

Now the task is to find out the status of the Alice energy in the end, if she moves optimally to save maximum energy.

Note : Her energy will not exceed more than 100 percent, and she will not move further if her energy goes down to 0 percent .

EXAMPLE : Let us suppose a grid of 4*4 as follow :

2 -2 2 -2

-2 2 -2 2

1 -1 1 -1

-1 1 -1 1

And if K= 10 meaning she has 10 percent energy at start. then after reaching 4th row she will be having 16 percent energy.One of the optimal move will be <1,2> -> <2,1> -> <3,2> -> <4,1>

So here answer is 16.

Upvotes: 0

Views: 235

Answers (1)

mcdowella
mcdowella

Reputation: 19601

I originally said you could solve this from the bottom up, but doing the example by hand I am going to work from the top down, because of the constraint that you cannot proceed once your energy goes down to zero - it doesn't come into play here, but it looks much easier to deal with if you are working from the top down. The principal is much the same - work row by row and at each stage write down the best score possible travelling through each cell, using the answers from the previous row to work out the answers for the current row.

We start out with 10, and I assume you can start out anywhere you want, so just subtract the top row from 10 to work out the best you can get to in the top row, including the energy difference from the cell you are now on. The top row becomes 8, 12, 8, 12.

The edge cells on the next row can only be reached in one way. The inner cells can be reached by two ways. In either case we work out the total there by taking account of the energy difference from that cell and the energy you could have from the cell you came from, taking the most promising choice when there are two. So we get 14, 10, 14, 10, where for example the second 14 is one of the 12ths above and to its left or above and two its right (if the scores were different we could take the best) combined with the -2 for that cell.

Similarly, we have 9, 15, 9, 15 for the next row and 16, 8, 16, 8 for the bottom, where for example the only way to get to the bottom left is from the 15 above and to its right, so adjusted by -1 we turn 15 into 16. There are two ways to get to the cell just to its right, but they both start from, 9, so adjusted by 1 we get 8.

If you need to whole path you can keep track of how you entered each cell as you work out the best cost to it, and then track your way up from the best answer when you are finished.

Upvotes: 1

Related Questions