top of page
Caută
Poza scriitoruluioanaunciuleanu

Find the length of the longest consecutive path from a given starting character in JAVA

Given a matrix of characters, find the length of the longest path starting from a character, in such a way that the characters are arranged in alphabetical order. You can mode in any direction from a cell.


Input: char character = 'a'; char[][] mat = {{'a', 'c', 'd'}, {'h', 'b', 'a'}, {'i', 'g', 'f'}}; Output: 4 Explanation: The longest consecutive path starting from a is: a, b, c, d.


Solution:


1. static int[] x = {0, 1, 1, -1, 1, 0, -1, -1}; 2. static int[] y = {1, 0, 1, 1, -1, -1, 0, -1}; 3. static int ROWS = 3; 4. static int COLUMNS = 3; 5. 6. static int[][] consecutivePaths = new int[ROWS][COLUMNS]; 7. 8. static boolean isValidCell(int row, int column) { 9. return row >= 0 && column >= 0 && row < ROWS && column < COLUMNS; 10. } 11. 12. static boolean isAdjacentCharacter(char previous, char current) { 13. return ((current - previous) == 1); 14. } 15. 16. static int getLength(char[][] characters, int row, int column, char previous) { 17. 18. if (!isValidCell(row, column) || !isAdjacentCharacter(previous, characters[row][column])) { 19. return 0; 20. } 21. 22. if (consecutivePaths[row][column] != -1) { 23. return consecutivePaths[row][column]; 24. } 25. 26. int longestPath = 0; 27. for (int i = 0; i < 8; i++) { 28. longestPath = Math.max(longestPath, 1 + getLength(characters, row + x[i], column + y[i], characters[row][column])); 29. } 30. return consecutivePaths[row][column] = longestPath; 31. } 32. 33. static int getConsecutivePathLength(char[][] characters, char character) { 34. for (int i = 0; i < ROWS; ++i) { 35. for (int j = 0; j < COLUMNS; ++j) { 36. consecutivePaths[i][j] = -1; 37. } 38. } 39. 40. int longestPath = 0; 41. for (int row = 0; row < ROWS; row++) { 42. for (int column = 0; column < COLUMNS; column++) { 43. if (characters[row][column] == character) { 44. for (int i = 0; i < 8; i++) { 45. longestPath = Math.max(longestPath, 1 + getLength(characters, row + x[i], column + y[i], character)); 46. } 47. } 48. } 49. } 50. return longestPath; 51. }

2 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no...

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...

Comentarios


bottom of page