I need help on this Homework . Please in Java .

Number of Optimal Pac Man Paths Filename: pacman.java Time Limit: 5 seconds (per input case) Standard Input, Standard Output A few years ago you wrote an app for your friend's new Phone, the newPhone. Since you grevw up on Pac Man, you wanted to write a simplified version of the game. In this game, the board was a rectangular grid and Pac Man started at the upper left-hand corner. His goal was to get to the lower right-hand corner. He always moved one square to the right or one square down. Each square he went to had a "goody" that's worth a particular amount of points. Your score was simply the sum of the scores of the goodies in each square you visited. For example, if the game board looked like this (P indicates Pac Man's starting location, and E indicates his ending location) 6 then Pac Man's optimal strategy would be to move right, down, right, right again, then down to yield a score of 3+4 +9+3-19 Upon reflecting on that first game, you now you realize that there might be more than one path that yields the maximum possible score for some input boards. You are curious just how many optimal paths a board might have. Furthermore, of those paths, you're also curious to determine the first alphabetic path that yields a maximum possible score. For the purposes of this problem, we describe a path as a string consisting only of letters D' or 'R', in the order that Pac Man moves. The string "RDRRD" represents the path shown above Write a program to satisfy your curiosity! The Problem Given a game board, determine the maximum possible score for Pac Man, the number of different paths that achieve that score and the first alphabetic path as described above that yields the maximum possible score. Two paths are considered different if one path contains a square that the other path does not contain. Number of Optimal Pac Man Paths Filename: pacman.java Time Limit: 5 seconds (per input case) Standard Input, Standard Output A few years ago you wrote an app for your friend's new Phone, the newPhone. Since you grevw up on Pac Man, you wanted to write a simplified version of the game. In this game, the board was a rectangular grid and Pac Man started at the upper left-hand corner. His goal was to get to the lower right-hand corner. He always moved one square to the right or one square down. Each square he went to had a "goody" that's worth a particular amount of points. Your score was simply the sum of the scores of the goodies in each square you visited. For example, if the game board looked like this (P indicates Pac Man's starting location, and E indicates his ending location) 6 then Pac Man's optimal strategy would be to move right, down, right, right again, then down to yield a score of 3+4 +9+3-19 Upon reflecting on that first game, you now you realize that there might be more than one path that yields the maximum possible score for some input boards. You are curious just how many optimal paths a board might have. Furthermore, of those paths, you're also curious to determine the first alphabetic path that yields a maximum possible score. For the purposes of this problem, we describe a path as a string consisting only of letters D' or 'R', in the order that Pac Man moves. The string "RDRRD" represents the path shown above Write a program to satisfy your curiosity! The Problem Given a game board, determine the maximum possible score for Pac Man, the number of different paths that achieve that score and the first alphabetic path as described above that yields the maximum possible score. Two paths are considered different if one path contains a square that the other path does not contain