<p>You are given a square <code>board</code>&nbsp;of characters. You can move on the board starting at the bottom right square marked with the character&nbsp;<code>&#39;S&#39;</code>.</p>

<p>You need&nbsp;to reach the top left square marked with the character <code>&#39;E&#39;</code>. The rest of the squares are labeled either with a numeric character&nbsp;<code>1, 2, ..., 9</code> or with an obstacle <code>&#39;X&#39;</code>. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.</p>

<p>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, <strong>taken modulo <code>10^9 + 7</code></strong>.</p>

<p>In case there is no path, return&nbsp;<code>[0, 0]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> board = ["E23","2X2","12S"]
<strong>Output:</strong> [7,1]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> board = ["E12","1X1","21S"]
<strong>Output:</strong> [4,2]
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> board = ["E11","XXX","11S"]
<strong>Output:</strong> [0,0]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= board.length == board[i].length &lt;= 100</code></li>
</ul>
class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        # starting state is bottom right corner, 'S'
        # any cell can be 1 - 9, X, E
        # up, left or up-left moves if there is no obstacle

        # each string in the list is equal length, of length n, where n is the side of the square
        # [max score, num_paths]
        # 2 <= n <= 100

        # 1. Calculate maximum score
        # [3, 3, 3]
        # [3, 3, 3,]
        # [3, 3, 3]
        # we could replace 'X' with -float("inf")

        N = len(board)
        scores = [[-float("inf")] * N for _ in range(N)]
        scores[-1][-1] = 0
        row, col = N - 1, N- 1
        for c in range(col - 1, -1, -1):
            if board[row][c] == 'X':
                continue
            scores[row][c] = max(scores[row][c], int(board[row][c]) + scores[row][c+1])
        for r in range(row - 1, -1, -1):
            if board[r][col] == 'X':
                continue
            scores[r][col] = max(scores[r][col], int(board[r][col]) + scores[r+1][col])
        # the initial states are filled out
        row -= 1
        col -= 1
        for r in range(row, -1, -1):
            for c in range(col, -1, -1):

                if board[r][c] == 'X':
                    continue
                max_score = max([scores[r+1][c+1], scores[r+1][c], scores[r][c+1]])
                if r == 0 and c == 0:
                    scores[r][c] = max_score
                else:
                    scores[r][c] = max_score + int(board[r][c])
        if scores[0][0] == -float("inf"):
            return [0, 0]
        max_score = scores[0][0]

        # if we have a current cell r, c
            # we're going to go to its neighbors, (r-1,c), (r, c-1), (r-1,c-1), but we're only going to visit each of the cells at most three times, so this is valid
        memo = {}
        board[-1] = board[-1][:-1] + '0'
        board[0] = '0' + board[0][1:]
        def dfs(r, c, score):
            if r == N - 1 and c == N - 1 and score == 0:
                return 1
            if r not in range(N) or c not in range(N) or board[r][c] == 'X' or score != scores[r][c]:
                return 0
            if (r, c) in memo:
                return memo[(r, c)]
            cur_cell = int(board[r][c])
            val = dfs(r + 1, c, score - cur_cell) + dfs(r, c + 1, score - cur_cell) + dfs(r + 1, c + 1, score - cur_cell)
            memo[(r, c)] = val
            return val
        paths = dfs(0, 0, max_score) % (10 ** 9 + 7)
        return [max_score,  paths]

            

        # 2. Find the number of maximum paths
        # we don't want to brute force every path because it is O(3^(n^2))
        # O(n^2)
        # 
19400