#1301

Number of Paths with Max Score

master · 1645 · lc hard +32 · verified · 42.2% accepted · 550 likes · top 23%

Description

You are on a square board. Start at the bottom-right cell marked 'S' and navigate to the top-left cell marked 'E'. Other cells hold digit characters (1–9) or an obstacle 'X'. From any cell, you may move up, left, or diagonally up-left — but never through an obstacle.

Return [maxScore, pathCount], where maxScore is the highest sum of digits collectible along any valid path, and pathCount is the number of paths achieving that score (modulo 10⁹ + 7). If no valid path exists, 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]

Code

1

2

3

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]: