top of page
Caută
Poza scriitoruluioanaunciuleanu

Minimum Initial Points to Reach Destination in JAVA

We have as an input a grid of cells with numbers. The numbers can be 0, positive or negative. To move across a cell, we must have positive points, meaning greater than 0 points. When we move to a new cell, we add that amount to out total points. We can only move from one cell to the right or down.


Input: int[][] points = {{-4, -8, 10}, {-5, -10, 2}, {10, 30, -7}}; Output: 10 Explanation: The initial minimum points to reach destination are 10 because we start from -4, we go to -5 and this equals to -9. After this point we have positive, high numbers, so those 2 points must be covered in the beginning. In order to have a positive number in order to be able to keep going, we add one, so we need 10 initial points: one to have positive number and 9 to make up for the negative value.



Solution:


1. static int minInitialPoints(int[][] points) { 2. int rows = points.length; 3. int columns = points[0].length; 4. int[][] minimumInitialPoints = new int[rows][columns]; 5. 6. minimumInitialPoints[rows - 1][columns - 1] = points[rows - 1][columns - 1] > 0 ? 1 : Math.abs(points[rows - 1][columns - 1]) + 1; 7. 8. for (int i = rows - 2; i >= 0; i--) { 9. minimumInitialPoints[i][columns - 1] = Math.max(minimumInitialPoints[i + 1][columns - 1] - points[i][columns - 1], 1); 10. } 11. for (int j = columns - 2; j >= 0; j--) { 12. minimumInitialPoints[rows - 1][j] = Math.max(minimumInitialPoints[rows - 1][j + 1] - points[rows - 1][j], 1); 13. } 14. 15. for (int i = rows - 2; i >= 0; i--) { 16. for (int j = columns - 2; j >= 0; j--) { 17. int minPoints = Math.min(minimumInitialPoints[i + 1][j], minimumInitialPoints[i][j + 1]); 18. minimumInitialPoints[i][j] = Math.max(minPoints - points[i][j], 1); 19. } 20. } 21. 22. return minimumInitialPoints[0][0]; 23. } 24.

2 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Comments


bottom of page