Thursday, September 3, 2015

Minimum Initial Points to Reach Destination


Given a grid with each cell consisting of positive, negative or no points i.e, zero points. 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).


Constraints :
  • 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
Example

Input: points[m][n] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };
Output: 7
Explanation: 
7 is the minimum value to reach destination with 
positive throughout the path. Below is the path.

(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)

We start from (0, 0) with 7, we reach(0, 1) 
with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)
with and finally we have 1 point (we needed 
greater than 0 points at the end). 

pasting the code below, please let me know if you found any bug in it.
import java.io.*;

class minInitialDP
{
    public static int max(int x, int y)
    {
        return (x>y?x:y);
    }

    public static int min(int x, int y)
    {
        return (x<y?x:y);
    }

    public static void main(String []args)
    {
        int points[][] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };

        int DP [][] = new int[3][3];

        // main code goes here 

        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                if (i==0 && j==0)
                {
                    DP[i][j] = 0;
                    continue;
                }

                if( i==0 )
                {
                    if(points[i][j-1] < 0)
                    {
                        DP[i][j] = -points[i][j-1]+DP[i][j-1]+1;       
                    }
                    else
                    {
                        DP[i][j] = DP[i][j-1];
                    }
                    continue;
                }

                if(j==0)
                {
                    if(points[i-1][j] < 0)
                        DP[i][j] = -points[i-1][j]+DP[i-1][j]+1;
                    else
                        DP[i][j] = DP[i-1][j];
                    continue;
                }

                int pi, pj;

                if(points[i][j-1] < 0)
                    pi = -points[i][j-1]+DP[i][j-1]+1;
                else
                    pi =  DP[i][j-1];

                if(points[i-1][j] < 0)
                    pj = -points[i-1][j]+DP[i-1][j]+1;
                else
                    pj = DP[i-1][j];

                DP[i][j] = min(pi, pj);
            }
        }

        for(int i=0; i<3; i++)
        {
            for(int j =0; j<3; j++)
                 System.out.print(DP[i][j] + " ");
            System.out.println("\n");
        }
    }

}

3 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. can u explain logic behind, and i guess it gives wrong output for
    int points[][] = {
    {-2, -3, -3, 4},
    {-5, -10, 1, 5},
    {10, 30, -5, 6},
    {11, 3, 5, 7},
    };

    ans is 8, it gives 9

    ReplyDelete