PROGRAMMING:Pac Man for your New Phone
You are writing an app for your friend’s new Phone, the newPhone. Since you grew up on Pac
Man, you want to write a simplified version of the game. In this game, the board is a rectangular
grid and Pac Man starts at the upper left-hand corner. His goal is to get to the lower right-hand
corner. He always moves one square to the right or one square down. Each square he goes to
has a “goody” that’s worth a particular amount of points. Your score is simply the sum of the
scores of the goodies in each square you have visited.
For example, if the game board looks like this (P indicates Pac Man’s starting location, and E
indicates his ending location):
![ QQ picture 20200719092700. PNG] (~ / 280f1819-a610-440c-afff-40938d3ee297. PNG)
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.
The Problem:
Given a game board, determine the maximum possible score for Pac Man.
###Input Description:
There will be multiple game boards in the input file. The first input line contains a positive
integer n, indicating the number of game boards to be processed. The first line of each game
board will contain two positive integers, r (0 < r < 100) and c (1 < c < 100), representing the
number of rows and columns for this game board. (The example above has three rows and four
columns.) Each of the following r input lines will contain c tokens, representing the contents of
that row. The first item on the first of these lines will be the character ‘P’, representing Pac
Man’s original location and the last item on the last line will be the character ‘E’, representing
P
3 2 8
1 4 9 3
6 2 2 E
two
Pac Man’s goal location. The rest of the items will be positive integers less than 1000. Items
will be separated by a single space on each line.
###Output Description:
At the beginning of each test case, output “Game Board #g:”, where g is the input board
number (starting from 1). For each game board, simply print out the maximum possible score for
the game.
Leave a blank line after the output for each test case. Follow the format illustrated in Sample
Output.
###Input example:
```in
two
3 4
P 3 2 8
1 4 9 3
6 2 2 E
2 2
P 5
401 E
```
###Output example:
```out
Game Board #1: 19
Game Board #2: 401
```
answer：If there is no answer, please comment
Man, you want to write a simplified version of the game. In this game, the board is a rectangular
grid and Pac Man starts at the upper left-hand corner. His goal is to get to the lower right-hand
corner. He always moves one square to the right or one square down. Each square he goes to
has a “goody” that’s worth a particular amount of points. Your score is simply the sum of the
scores of the goodies in each square you have visited.
For example, if the game board looks like this (P indicates Pac Man’s starting location, and E
indicates his ending location):
![ QQ picture 20200719092700. PNG] (~ / 280f1819-a610-440c-afff-40938d3ee297. PNG)
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.
The Problem:
Given a game board, determine the maximum possible score for Pac Man.
###Input Description:
There will be multiple game boards in the input file. The first input line contains a positive
integer n, indicating the number of game boards to be processed. The first line of each game
board will contain two positive integers, r (0 < r < 100) and c (1 < c < 100), representing the
number of rows and columns for this game board. (The example above has three rows and four
columns.) Each of the following r input lines will contain c tokens, representing the contents of
that row. The first item on the first of these lines will be the character ‘P’, representing Pac
Man’s original location and the last item on the last line will be the character ‘E’, representing
P
3 2 8
1 4 9 3
6 2 2 E
two
Pac Man’s goal location. The rest of the items will be positive integers less than 1000. Items
will be separated by a single space on each line.
###Output Description:
At the beginning of each test case, output “Game Board #g:”, where g is the input board
number (starting from 1). For each game board, simply print out the maximum possible score for
the game.
Leave a blank line after the output for each test case. Follow the format illustrated in Sample
Output.
###Input example:
```in
two
3 4
P 3 2 8
1 4 9 3
6 2 2 E
2 2
P 5
401 E
```
###Output example:
```out
Game Board #1: 19
Game Board #2: 401
```
answer：If there is no answer, please comment