Number of Paths with Max Score
You are given a square board of characters. You can move on the board starting at the bottom-right square marked with the character 'S'.
You need to reach the top-left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move, you can go up, left, or up-left diagonally only if there is no obstacle there.
Return a list of two integers:
- The first integer is the maximum sum of numeric characters you can collect.
- The second integer is the number of such paths that achieve that maximum sum, taken modulo
10^9 + 7.
In case there is no path, return [0, 0].
Example 1
Input
board = ["E23","2X2","12S"]Output
[7,1]The maximum collectible sum is 7, and there is exactly one path that achieves it.
Example 2
Input
board = ["E12","1X1","21S"]Output
[4,2]The maximum collectible sum is 4, and there are two paths that achieve it.
Constraints
- 2 <= board.length == board[i].length <= 100