1import java.util.List;
2import java.util.Arrays;
3
4class Solution {
5    private List<String> board;
6    private int boardSize;
7    private int[][] maxScoreGrid;
8    private int[][] pathsCountGrid;
9    private final int MOD = (int) 1e9 + 7; // Define the MOD constant for path count calculations
10
11    public int[] pathsWithMaxScore(List<String> board) {
12        boardSize = board.size();
13        this.board = board;
14        maxScoreGrid = new int[boardSize][boardSize];
15        pathsCountGrid = new int[boardSize][boardSize];
16
17        // Initialize grid values to -1 indicating unreachable cells
18        for (int[] row : maxScoreGrid) {
19            Arrays.fill(row, -1);
20        }
21
22        // Starting point at the bottom-right has a score of 0 and 1 path.
23        maxScoreGrid[boardSize - 1][boardSize - 1] = 0;
24        pathsCountGrid[boardSize - 1][boardSize - 1] = 1;
25
26        // Calculate maximum score and paths count from bottom-right to top-left
27        for (int i = boardSize - 1; i >= 0; --i) {
28            for (int j = boardSize - 1; j >= 0; --j) {
29                updateScoresAndPaths(i, j, i + 1, j);
30                updateScoresAndPaths(i, j, i, j + 1);
31                updateScoresAndPaths(i, j, i + 1, j + 1);
32                if (maxScoreGrid[i][j] != -1) {
33                    char cell = board.get(i).charAt(j);
34                    if (cell >= '0' && cell <= '9') {
35                        maxScoreGrid[i][j] += (cell - '0'); // Update score for numeric cells
36                    }
37                }
38            }
39        }
40
41        // Prepare and return the results
42        int[] result = new int[2];
43        if (maxScoreGrid[0][0] != -1) {
44            result[0] = maxScoreGrid[0][0]; // Maximum score
45            result[1] = pathsCountGrid[0][0]; // Number of paths with the maximum score
46        }
47        return result;
48    }
49
50    // Helper function to update the maximum score and paths count
51    private void updateScoresAndPaths(int currentRow, int currentCol, int prevRow, int prevCol) {
52        // Skip update if out of bounds, previous cell was unreachable, or current cell is blocked or the start
53        if (prevRow >= boardSize || prevCol >= boardSize
54            || maxScoreGrid[prevRow][prevCol] == -1
55            || board.get(currentRow).charAt(currentCol) == 'X'
56            || board.get(currentRow).charAt(currentCol) == 'S') {
57            return;
58        }
59      
60        // Update if a higher score is found
61        if (maxScoreGrid[prevRow][prevCol] > maxScoreGrid[currentRow][currentCol]) {
62            maxScoreGrid[currentRow][currentCol] = maxScoreGrid[prevRow][prevCol];
63            pathsCountGrid[currentRow][currentCol] = pathsCountGrid[prevRow][prevCol];
64        }
65        // If the current score is equal, add the paths count
66        else if (maxScoreGrid[prevRow][prevCol] == maxScoreGrid[currentRow][currentCol]) {
67            pathsCountGrid[currentRow][currentCol] = (pathsCountGrid[currentRow][currentCol] + pathsCountGrid[prevRow][prevCol]) % MOD;
68        }
69    }
70}
71

1#include <vector>
2#include <string>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    vector<int> pathsWithMaxScore(vector<string>& board) {
9        int n = board.size(); // Get the size of the board
10        const int mod = 1e9 + 7; // Modulus for the number of ways to avoid integer overflow
11        int maxScores[n][n]; // Matrix to store the maximum scores up to each cell
12        int ways[n][n]; // Matrix to store the number of ways to reach each cell with the max score
13        // Initialize matrices with -1 for scores and 0 for ways
14        memset(maxScores, -1, sizeof(maxScores));
15        memset(ways, 0, sizeof(ways));
16
17        // Starting point (bottom-right of the board)
18        maxScores[n - 1][n - 1] = 0;
19        ways[n - 1][n - 1] = 1;
20
21        // Lambda function to update scores and ways for current (i, j) from neighbor (x, y)
22        auto update = [&](int i, int j, int x, int y) {
23            // Don't proceed if out of bounds, unreachable, or starting point
24            if (x >= n || y >= n || maxScores[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S') {
25                return;
26            }
27            // If the score from neighbor (x, y) is greater, update current cell (i, j)
28            if (maxScores[x][y] > maxScores[i][j]) {
29                maxScores[i][j] = maxScores[x][y];
30                ways[i][j] = ways[x][y];
31            } 
32            // If equal, add to the number of ways
33            else if (maxScores[x][y] == maxScores[i][j]) {
34                ways[i][j] = (ways[i][j] + ways[x][y]) % mod;
35            }
36        };
37
38        // Iterate through the board in reverse order
39        for (int i = n - 1; i >= 0; --i) {
40            for (int j = n - 1; j >= 0; --j) {
41                // Update current cell based on the three possible moves
42                update(i, j, i + 1, j); // Down
43                update(i, j, i, j + 1); // Right
44                update(i, j, i + 1, j + 1); // Diagonally
45                // Add score for the current cell if it's a digit
46                if (maxScores[i][j] != -1 && board[i][j] >= '0' && board[i][j] <= '9') {
47                    maxScores[i][j] += (board[i][j] - '0');
48                }
49            }
50        }
51
52        // Prepare the answer in a vector
53        vector<int> answer(2);
54        if (maxScores[0][0] != -1) { // If the top-left cell is reachable
55            answer[0] = maxScores[0][0]; // Maximum score
56            answer[1] = ways[0][0]; // Number of ways
57        }
58        return answer;
59    }
60};
61

1// TypeScript does not have an exact equivalent of C++'s <vector>, so we'll use arrays.
2// The input board is an array of strings representing the game board.
3
4// Define constants for dimensions and modulus.
5const MOD = 1e9 + 7;
6
7// Function to calculate the paths with max score from the given board.
8function pathsWithMaxScore(board: string[]): number[] {
9    const n: number = board.length; // Get the size of the board.
10    let maxScores: number[][] = []; // Matrix to store the maximum scores to each cell.
11    let ways: number[][] = []; // Matrix to store the number of ways to reach each cell with the max score.
12
13    // Initialize the matrices.
14    for (let i = 0; i < n; i++) {
15        maxScores[i] = [];
16        ways[i] = [];
17        for (let j = 0; j < n; j++) {
18            maxScores[i][j] = -1; // Initialize scores with -1.
19            ways[i][j] = 0; // Initialize ways with 0.
20        }
21    }
22
23    // Starting point (bottom-right of the board).
24    maxScores[n - 1][n - 1] = 0;
25    ways[n - 1][n - 1] = 1;
26
27    // Lambda function to update scores and ways for the current cell from neighbor.
28    const update = (i: number, j: number, x: number, y: number) => {
29        // Don't proceed if out of bounds, unreachable, or at the starting point.
30        if (x >= n || y >= n || maxScores[x][y] === -1 || board[i][j] === 'X' || board[i][j] === 'S') {
31            return;
32        }
33        // If the score from the neighbor is greater, update the current cell.
34        if (maxScores[x][y] > maxScores[i][j]) {
35            maxScores[i][j] = maxScores[x][y];
36            ways[i][j] = ways[x][y];
37        }
38        // If the score is equal, add to the number of ways.
39        else if (maxScores[x][y] === maxScores[i][j]) {
40            ways[i][j] = (ways[i][j] + ways[x][y]) % MOD;
41        }
42    };
43
44    // Iterate through the board in reverse order to find max scores and ways.
45    for (let i = n - 1; i >= 0; --i) {
46        for (let j = n - 1; j >= 0; --j) {
47            // Update the current cell based on the three possible moves: down, right, and diagonally.
48            update(i, j, i + 1, j); // Down
49            update(i, j, i, j + 1); // Right
50            update(i, j, i + 1, j + 1); // Diagonally
51            // Add the score for the current cell if it's a digit.
52            if (maxScores[i][j] !== -1 && !isNaN(parseInt(board[i][j]))) {
53                maxScores[i][j] += parseInt(board[i][j]);
54            }
55        }
56    }
57
58    // Prepare the answer in an array.
59    let answer: number[] = [0, 0]; // Initialize answer with 0s for cases where the top-left cell is not reachable.
60    if (maxScores[0][0] !== -1) { // If the top-left cell is reachable.
61        answer[0] = maxScores[0][0]; // Maximum score.
62        answer[1] = ways[0][0]; // Number of ways.
63    }
64    return answer;
65}
66
67// Example usage:
68// const board: string[] = ['E23', '2X2', '12S'];
69// pathsWithMaxScore(board); // Should return the max score and number of ways to reach the end.
70