Problem Explanation

In this problem, you are given a square board of characters. You start at the bottom right square which is marked with 'S'. Your aim is to reach the top left square, marked with 'E'. The squares in between can be given either a numeric character 1, 2, ..., 9 or an obstacle 'X'. You can only go up, left or up-left (diagonally) if there is no obstacle there.

Your task is to find the maximum sum of numeric characters you can collect in your journey from 'S' to 'E' and the number of such paths that you can take to get that maximum sum. The count of paths is calculated modulo 10^9 + 7. If there is no possible path, you should return [0,0].

For example, considering the following input board:

1
2
3    ["E23", 
4    "2X2", 
5    "12S"]

The maximum sum you can achieve is 7 and there is only one way to reach that sum, hence you would return [7, 1].

Approach Explanation

The approach used to solve this problem is dynamic programming. Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

The algorithm captures the notion of an optimal path through a decision process, which in this case is moving from the starting point to the destination, possibly going through some restricted paths and/or obstacles.

For each grid cell, calculate the maximum sum it can provide and also count the number of such paths from starting point to that cell. We do this by comparing and storing values in the cell regarding the 3 positions it can possibly move to (up, left or up-left). For each of these directions, we pick the maximum possible sum and update the count of paths for the current cell accordingly.

In case there is an obstacle (marked as 'X'), we simply continue to the next cell because we cannot move to that cell. Also, if the selected move points to the starting cell 'S', we do not add any value to the sum because the starting cell does not contribute to the sum.

Finally, we return the maximum sum and the count of paths from (0,0) position.

Python Solution

1
2python
3class Solution:
4    def pathsWithMaxScore(self, board):
5        MOD = 10**9 + 7
6        n = len(board)
7        dp_sum = [[0]*(n+1) for _ in range(n+1)]
8        dp_cnt = [[0]*(n+1) for _ in range(n+1)]
9        dp_cnt[n-1][n-1] = 1
10
11        for x in range(n-1, -1, -1):
12            for y in range(n-1, -1, -1):
13                if dp_cnt[x][y]:
14                    for dx, dy in [(x-1, y), (x, y-1), (x-1, y-1)]:
15                        if 0<=dx<n and 0<=dy<n and board[dx][dy] != 'X':
16                            ndp = dp_sum[x][y] + (0 if board[dx][dy]=='E' else int(board[dx][dy]))
17                            if ndp > dp_sum[dx][dy]:
18                                dp_sum[dx][dy] = ndp
19                                dp_cnt[dx][dy] = dp_cnt[x][y]
20                            elif ndp == dp_sum[dx][dy]:
21                                dp_cnt[dx][dy] += dp_cnt[x][y]
22                            dp_cnt[dx][dy] %= MOD
23
24        return [dp_sum[0][0], dp_cnt[0][0]]

In the Python Solution, we use two 2d-arrays dp_sum and dp_cnt to store the maximum sum and the count of paths respectively. The nested for loop is used to iterate through the cells of the board in reverse order (starting from 'S' and moving towards 'E'). The if condition if dp_cnt[x][y]: checks whether there is a path from 'S' to the current cell. If there is a path, for each possible position (i.e., up, left and up-left), if it is inside the board and is not a hurdle, we calculate a new sum. We further check, if this new sum is greater than the maximum obtained till now then we update the maximum sum and the number of paths; or if this new sum is equal to the current maximum sum, we simply update the number of paths.# JavaScript Solution

In JavaScript, we can use a similar approach of dynamic programming to solve the problem. Please take a look at the solution below:

1
2javascript
3var pathsWithMaxScore = function(board) {
4    let n = board.length, MOD = 1e9 + 7;
5    let dp = new Array(n+1).fill(0).map(x=> new Array(n+1).fill(0));
6    let cnt = new Array(n+1).fill(0).map(x=> new Array(n+1).fill(0));
7    dp[n][n-1] = 0, cnt[n-1][n-1] = 1;
8    for(let i=n-1;i>=0;i--){
9        for(let j=n-1;j>=0;j--){
10            dp[i][j] = Math.max(dp[i+1][j],dp[i][j+1],dp[i+1][j+1]);
11            if(board[i][j] === 'X') continue;
12            if(board[i][j] !== 'E') dp[i][j] += parseInt(board[i][j]);
13            if(dp[i+1][j] === dp[i][j]) cnt[i][j] = (cnt[i][j] + cnt[i+1][j]) % MOD;
14            if(dp[i][j+1] === dp[i][j]) cnt[i][j] = (cnt[i][j] + cnt[i][j+1]) % MOD;
15            if(dp[i+1][j+1] === dp[i][j]) cnt[i][j] = (cnt[i][j] + cnt[i+1][j+1]) % MOD;
16        }
17    }
18    return [dp[0][0],cnt[0][0]];
19};

The JavaScript solution here also makes use of two 2D arrays, dp and cnt to store the maximum sum and the count of paths respectively. We run nested for loops to traverse the board in reverse order. If the current cell contains 'X', we skip over it. We then calculate the maximum sum achieved thus far and update the count of paths accordingly for every direction (up, left and diagonally - up-left).

Java Solution

A similar approach can be taken in Java as well. Below is the Java code for the problem:

1
2java
3class Solution {
4    public int[] pathsWithMaxScore(List<String> board) {
5        int MOD = 1000000007, n = board.size();
6        int [][][] dp = new int[n+1][n+1][2];
7        dp[n-1][n-1][1] = 1; // number of ways to reach (i, j)
8
9        for(int i=n-1; i>=0; i--)
10            for(int j=n-1; j>=0; j--)
11                if(dp[i][j][1]>0)
12                    for(int ni : new int []{i-1, i, i-1})
13                        for(int nj : new int []{j-1, j-1, j})
14                            if(ni>=0 && nj>=0 && board.get(ni).charAt(nj) != 'X'){
15                                int add = board.get(ni).charAt(nj) - '0';
16                                if(i == n-1 && j == n-1) add = 0;
17                                int next = dp[i][j][0] + add;
18                                if(next > dp[ni][nj][0]){
19                                    dp[ni][nj][0] = next;
20                                    dp[ni][nj][1] = dp[i][j][1];
21                                }
22                                else if(next == dp[ni][nj][0])
23                                    dp[ni][nj][1] = (dp[ni][nj][1]+dp[i][j][1]) % MOD;
24                            }
25        if(board.get(0).charAt(0) == 'X' || dp[0][0][1] == 0) return new int[]{0, 0};
26        return dp[0][0];
27    }
28}

The Java solution uses a 3D array, dp, where dp[i][j][0] stores the maximum sum and dp[i][j][1] stores the count of paths till (i,j). The two nested for loops traverse the board in reverse order. They calculate the maximum total sum and the number of ways to achieve it in each cell, also considering the cells that can be reached from the current cell (up, left and diagonally - up-left). If the cell contains an 'X' or there are no pathways to reach the destination, it returns [0,0].