top of page
Caută
Poza scriitoruluioanaunciuleanu

Collect maximum points in a grid using two traversals in JAVA

Using a grid of cells that holds values, try to find the maximum number of points that can be summed by using two traversals. The first traversal starts from the top left corner and ends in the bottom left corner. The second traversal starts from the top right corner and ends in the bottom right corner. You can move from one cell to the other in only three ways: down one cell, down one cell in a diagonal to the left, or down one cell in a diagonal to the right. If a cell is being visited by both traversals, then its value will be added to the sum only once.

Input: int[][] startArray = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}, {17, 18, 19, 20} }; Output: 109 Explanation: The first traversal is: 1, 6, 11, 14, 17. The second one is: 4, 8, 12, 16, 20.


Solution:


1. static final int ROW = 5; 2. static final int COLUMN = 4; 3. 4. static boolean isValidInput(int x, int y1, int y2) { 5. return ((x >= 0) && (x < ROW) && (y1 >= 0) && (y1 < COLUMN) && (y2 >= 0) && (y2 < COLUMN)); 6. } 7. 8. static int getMaxValue(int[][] startArray, int[][][] intermediaryValues, int x, int y1, int y2) { 9. if (!isValidInput(x, y1, y2)) { 10. return Integer.MIN_VALUE; 11. } 12. 13. if (x == ROW - 1 && y1 == 0 && y2 == COLUMN - 1) { 14. return startArray[x][y1] + startArray[x][y2]; 15. } 16. 17. if (x == ROW - 1) { 18. return Integer.MIN_VALUE; 19. } 20. 21. if (intermediaryValues[x][y1][y2] != -1) { 22. return intermediaryValues[x][y1][y2]; 23. } 24. 25. int answer = Integer.MIN_VALUE; 26. 27. int temporary = (y1 == y2) ? startArray[x][y1] : startArray[x][y1] + startArray[x][y2]; 28. 29. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2 - 1)); 30. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2 + 1)); 31. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2)); 32. 33. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2)); 34. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2 - 1)); 35. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2 + 1)); 36. 37. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2)); 38. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2 - 1)); 39. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2 + 1)); 40. 41. return (intermediaryValues[x][y1][y2] = answer); 42. } 43. 44. static int geMaxCollectionValue(int[][] arr) { 45. int[][][] intermediaryValues = new int[ROW][COLUMN][COLUMN]; 46. for (int i = 0; i < ROW; i++) { 47. for (int j = 0; j < COLUMN; j++) { 48. for (int l = 0; l < COLUMN; l++) 49. intermediaryValues[i][j][l] = -1; 50. } 51. } 52. 53. return getMaxValue(arr, intermediaryValues, 0, 0, COLUMN - 1); 54. } 55.

3 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