What are the Minimum Initial Points to Reach Destination ?

To begin from the upper left corner of a given framework, one needs to achieve the base right corner.
Every cell in the grid contains a number, the number may positive or negative.
We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points.
We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :

- From a cell (i, j) we can move to (i+1, j) or (i, j+1).
- We cannot move from (i, j) if your overall points at (i, j) is <= 0.
- We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.

Syntax

minInitTokens(matrix)

Sample Code in C++

[pastacode lang=”cpp” manual=”%23include%3Ciostream%3E%0A%23include%3Ccmath%3E%0A%23define%20ROW%203%0A%23define%20COL%203%0Ausing%20namespace%20std%3B%0A%0Aint%20tokens%5BROW%5D%5BCOL%5D%20%3D%20%7B%0A%20%20%20%7B-2%2C-3%2C3%7D%2C%0A%20%20%20%7B-5%2C-10%2C1%7D%2C%0A%20%20%20%7B10%2C30%2C-5%7D%0A%7D%3B%0A%0Aint%20max(int%20a%2C%20int%20b)%20%7B%0A%20%20%20return%20(a%3Eb)%3Fa%3Ab%3B%0A%7D%0A%0Aint%20minInitPoints()%20%7B%0A%20%20%20int%20minToken%5BROW%5D%5BCOL%5D%3B%0A%20%20%20int%20m%20%3D%20ROW%2C%20n%20%3D%20COL%3B%0A%20%20%20%0A%20%20%20minToken%5Bm-1%5D%5Bn-1%5D%20%3D%20tokens%5Bm-1%5D%5Bn-1%5D%20%3E%200%3F%201%3A%20abs(tokens%5Bm-1%5D%5Bn-1%5D)%20%2B%201%3B%0A%20%20%20%0A%20%20%20for%20(int%20i%20%3D%20m-2%3B%20i%20%3E%3D%200%3B%20i–)%20%20%20%20%2F%2Ffrom%20last%20row%20to%20first%20row%2C%20fill%20points%0A%20%20%20%20%20%20minToken%5Bi%5D%5Bn-1%5D%20%3D%20max(minToken%5Bi%2B1%5D%5Bn-1%5D%20-%20tokens%5Bi%5D%5Bn-1%5D%2C%201)%3B%0A%20%20%20%0A%20%20%20for%20(int%20j%20%3D%20n-2%3B%20j%20%3E%3D%200%3B%20j–)%20%20%20%20%2F%2Ffill%20last%20column%20to%20first%20column%2C%20fill%20points%0A%20%20%20%20%20%20minToken%5Bm-1%5D%5Bj%5D%20%3D%20max(minToken%5Bm-1%5D%5Bj%2B1%5D%20-%20tokens%5Bm-1%5D%5Bj%5D%2C%201)%3B%0A%0A%20%20%20for%20(int%20i%3Dm-2%3B%20i%3E%3D0%3B%20i–)%20%7B%0A%20%20%20%20%20%20for%20(int%20j%3Dn-2%3B%20j%3E%3D0%3B%20j–)%20%7B%0A%20%20%20%20%20%20%20%20%20int%20remPoint%20%3D%20min(minToken%5Bi%2B1%5D%5Bj%5D%2C%20minToken%5Bi%5D%5Bj%2B1%5D)%3B%20%20%20%20%2F%2Fcalculate%20remaining%20points%0A%20%20%20%20%20%20%20%20%20minToken%5Bi%5D%5Bj%5D%20%3D%20max(remPoint%20-%20tokens%5Bi%5D%5Bj%5D%2C%201)%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%7D%0A%20%20%20return%20minToken%5B0%5D%5B0%5D%3B%0A%7D%0A%0Aint%20main()%20%7B%0A%20%20%20cout%20%3C%3C%20%22Least%20Points%20Required%3A%20%22%20%3C%3C%20minInitPoints()%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output

Least Points Required: 7

What are the Minimum Initial Points to Reach Destination ?