Algorithm Class - Matrix Path Problem 4

Seojun is working as a teaching assistant for a dynamic programming class again. Let us check through a problem whether the students understood what his father taught in class.

An n × n matrix m of positive integers is given. Starting at the top-left cell, you move one cell at a time until you reach the bottom-right cell. The sum of the numbers in the cells you visit along the way is the score of that path. The movement rules are as follows.

• You can move only right or down.
• Moves left, up, or diagonally are not allowed.

The pseudocode for the matrix path problem, which finds the highest score among all paths from cell (1, 1) to cell (n, n) of the matrix, is given below. Starting from the start cell (1, 1), you must pass through at least one of the P intermediate cells before reaching the end cell (n, n). Find the highest score and help Seojun.

The dynamic programming pseudocode for the matrix path problem is as follows.

matrix_path(m[][], n) {  # Finds the highest score from (1, 1) to (n, n).
    for i <- 0 to n
        d[i, 0] <- 0;
    for j <- 1 to n
        d[0, j] <- 0;
    for i <- 1 to n
        for j <- 1 to n
            d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]);
    return d[n, n];
}

The first line gives the size of the matrix n (5 ≤ n ≤ 1,000).

The next n lines each contain n integers representing one row of the matrix, separated by single spaces. Each cell value is between 1 and 100,000 inclusive.

The next line gives P (1 ≤ P ≤ n² - 2).

The next P lines each give the row number ri and column number ci of a distinct intermediate cell (1 ≤ ri, ci ≤ n, (ri, ci) ≠ (1, 1), (ri, ci) ≠ (n, n)).

Print the highest score over paths that start at the start cell (1, 1), pass through at least one of the P intermediate cells, and then reach the end cell (n, n).