Algorithm Class - Matrix Path Problem 3

Seojun is once again a teaching assistant for the dynamic programming class. 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, we move one cell at a time to reach the bottom-right cell. 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.
• Moves to the left, upward, or diagonally are not allowed.

The pseudocode for the matrix path problem, which computes the highest score among all paths from cell (1, 1) to (n, n), is given below. Help our Seojun by computing, respectively, the highest score of a path from the start cell (1, 1) that passes through the intermediate cell Y and reaches the end cell (n, n), and the highest score of a path from the start cell (1, 1) that reaches the end cell (n, n) without passing through the intermediate cell Y.

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

matrix_path(m[][], n) {  # compute 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 value in a cell is between 1 and 100,000 inclusive.

The next line gives the row number r and column number c of the intermediate cell Y (1 ≤ r, c ≤ n, (r, c) ≠ (1, 1), (r, c) ≠ (n, n)).

Print two integers on the first line. The first integer is the highest score of a path from the start cell (1, 1) that passes through the intermediate cell Y and reaches the end cell (n, n). The second integer is the highest score of a path from the start cell (1, 1) that reaches the end cell (n, n) without passing through the intermediate cell Y.