Algorithm Class - Matrix Path Problem 7

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

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

• We can move only to the right or downward.
• Moving left, upward, or diagonally is not allowed.

The pseudocode for the matrix path problem, which finds the highest score among all paths from cell (1, 1) to (n, n), is given below. Starting at the source cell (1, 1) and reaching the destination cell (n, n), find the highest score and, among the paths with the highest score, the case that passes through as many of the P intermediate cells as possible, and help our Seojun. It is possible that every path with the highest score passes through no intermediate cell at all.

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

matrix_path(m[][], n) {  # find 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 a single space. Each cell holds the value 1 or 2.

The next line gives P. (1 ≤ P ≤ n2 - 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))

On the first line, output two integers. The first integer is the highest score from the source cell (1, 1) to the destination cell (n, n).

The second integer is the maximum number of intermediate cells contained in a path with the highest score. If every path with the highest score passes through no intermediate cell at all, output 0.