{x}
blog image

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, and the second is the number of such paths that you can take to get 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]

Example 2:

Input: board = ["E12","1X1","21S"]
Output: [4,2]

Example 3:

Input: board = ["E11","XXX","11S"]
Output: [0,0]

 

Constraints:

  • 2 <= board.length == board[i].length <= 100

Solution Explanation:

This problem asks to find the maximum sum of numeric characters collected while traversing a board from the bottom-right ('S') to the top-left ('E'), moving only up, left, or diagonally up-left, avoiding obstacles ('X'). The solution also needs to count the number of paths achieving this maximum sum.

The optimal approach is dynamic programming. We use two 2D arrays:

  • f[i][j]: Stores the maximum score achievable when reaching cell (i, j).
  • g[i][j]: Stores the number of paths achieving the maximum score at cell (i, j).

The algorithm iterates through the board from bottom-right to top-left. For each cell (i, j):

  1. Initialization: f[n-1][n-1] = 0, g[n-1][n-1] = 1 (starting point). All other f[i][j] are initialized to -1 (representing unreachable).

  2. Update: We consider three possible previous cells: (i+1, j), (i, j+1), (i+1, j+1). If a previous cell (x, y) is valid (within bounds, not an obstacle, and reachable – f[x][y] != -1), we update f[i][j] and g[i][j] as follows:

    • If f[x][y] > f[i][j], it means a better path is found. Update f[i][j] = f[x][y] and g[i][j] = g[x][y].
    • If f[x][y] == f[i][j], it means another path with the same maximum score is found. Update g[i][j] = g[i][j] + g[x][y].

  3. Add Cell Value: If the current cell (i, j) contains a digit, add its value to f[i][j].

  4. Modulo Operation: The count of paths (g[i][j]) is updated using the modulo operator (% (10^9 + 7)) to prevent integer overflow.

  5. Result: Finally, f[0][0] contains the maximum score, and g[0][0] contains the number of paths achieving that score. If f[0][0] is still -1, there's no path to the endpoint, so we return [0, 0].

Time and Space Complexity Analysis:

  • Time Complexity: O(n^2), where n is the size of the board. We iterate through each cell once.
  • Space Complexity: O(n^2), due to the use of the f and g arrays.

Code in Different Languages:

The code implementations provided in the original response are already quite comprehensive and well-explained. They cover Python3, Java, C++, and Go. I won't reproduce them here to avoid redundancy, but the above explanation should clarify their functionality and logic. The key is understanding the dynamic programming approach and how the f and g arrays are used to track the maximum score and the number of paths.