1301. Number of Paths with Max Score

class Solution {
    private static final int MOD = 1_000_000_007;

    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();

        int[][] score = new int[n][n];
        int[][] ways = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(score[i], -1);
        }

        score[n - 1][n - 1] = 0;
        ways[n - 1][n - 1] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (board.get(i).charAt(j) == 'X') continue;
                if (i == n - 1 && j == n - 1) continue;

                int best = -1;
                int count = 0;

                int[][] dir = {{1, 0}, {0, 1}, {1, 1}};

                for (int[] d : dir) {
                    int ni = i + d[0];
                    int nj = j + d[1];

                    if (ni >= n || nj >= n) continue;
                    if (score[ni][nj] == -1) continue;

                    if (score[ni][nj] > best) {
                        best = score[ni][nj];
                        count = ways[ni][nj];
                    } else if (score[ni][nj] == best) {
                        count = (count + ways[ni][nj]) % MOD;
                    }
                }

                if (best == -1) continue;

                char ch = board.get(i).charAt(j);
                if (ch != 'E' && ch != 'S') {
                    best += ch - '0';
                }

                score[i][j] = best;
                ways[i][j] = count;
            }
        }

        if (ways[0][0] == 0) return new int[]{0, 0};

        return new int[]{score[0][0], ways[0][0]};
    }
}

class Solution:
    MOD = 10 ** 9 + 7

    def pathsWithMaxScore(self, board):

        n = len(board)

        score = [[-1] * n for _ in range(n)]
        ways = [[0] * n for _ in range(n)]

        score[n - 1][n - 1] = 0
        ways[n - 1][n - 1] = 1

        directions = [(1, 0), (0, 1), (1, 1)]

        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):

                if board[i][j] == 'X':
                    continue

                if i == n - 1 and j == n - 1:
                    continue

                best = -1
                cnt = 0

                for dx, dy in directions:

                    ni = i + dx
                    nj = j + dy

                    if ni >= n or nj >= n:
                        continue

                    if score[ni][nj] == -1:
                        continue

                    if score[ni][nj] > best:
                        best = score[ni][nj]
                        cnt = ways[ni][nj]

                    elif score[ni][nj] == best:
                        cnt = (cnt + ways[ni][nj]) % self.MOD

                if best == -1:
                    continue

                ch = board[i][j]

                if ch not in ('E', 'S'):
                    best += int(ch)

                score[i][j] = best
                ways[i][j] = cnt

        if ways[0][0] == 0:
            return [0, 0]

        return [score[0][0], ways[0][0]]

class Solution {
public:
    const int MOD = 1e9 + 7;

    vector<int> pathsWithMaxScore(vector<string>& board) {

        int n = board.size();

        vector<vector<int>> score(n, vector<int>(n, -1));
        vector<vector<int>> ways(n, vector<int>(n, 0));

        score[n - 1][n - 1] = 0;
        ways[n - 1][n - 1] = 1;

        vector<pair<int,int>> dir = {{1,0},{0,1},{1,1}};

        for(int i = n - 1; i >= 0; i--) {

            for(int j = n - 1; j >= 0; j--) {

                if(board[i][j] == 'X') continue;

                if(i == n - 1 && j == n - 1) continue;

                int best = -1;
                int cnt = 0;

                for(auto &d : dir){

                    int ni = i + d.first;
                    int nj = j + d.second;

                    if(ni >= n || nj >= n) continue;

                    if(score[ni][nj] == -1) continue;

                    if(score[ni][nj] > best){
                        best = score[ni][nj];
                        cnt = ways[ni][nj];
                    }
                    else if(score[ni][nj] == best){
                        cnt = (cnt + ways[ni][nj]) % MOD;
                    }
                }

                if(best == -1) continue;

                if(board[i][j] != 'E' && board[i][j] != 'S'){
                    best += board[i][j] - '0';
                }

                score[i][j] = best;
                ways[i][j] = cnt;
            }
        }

        if(ways[0][0] == 0) return {0,0};

        return {score[0][0], ways[0][0]};
    }
};

var pathsWithMaxScore = function(board) {

    const MOD = 1000000007;
    const n = board.length;

    const score = Array.from({length: n}, () => Array(n).fill(-1));
    const ways = Array.from({length: n}, () => Array(n).fill(0));

    score[n - 1][n - 1] = 0;
    ways[n - 1][n - 1] = 1;

    const dir = [[1,0],[0,1],[1,1]];

    for(let i = n - 1; i >= 0; i--){

        for(let j = n - 1; j >= 0; j--){

            if(board[i][j] === 'X') continue;

            if(i === n - 1 && j === n - 1) continue;

            let best = -1;
            let cnt = 0;

            for(const [dx,dy] of dir){

                const ni = i + dx;
                const nj = j + dy;

                if(ni >= n || nj >= n) continue;

                if(score[ni][nj] === -1) continue;

                if(score[ni][nj] > best){
                    best = score[ni][nj];
                    cnt = ways[ni][nj];
                }
                else if(score[ni][nj] === best){
                    cnt = (cnt + ways[ni][nj]) % MOD;
                }
            }

            if(best === -1) continue;

            const ch = board[i][j];

            if(ch !== 'E' && ch !== 'S'){
                best += Number(ch);
            }

            score[i][j] = best;
            ways[i][j] = cnt;
        }
    }

    if(ways[0][0] === 0) return [0,0];

    return [score[0][0], ways[0][0]];
};