Collect maximum points in a grid using two traversals

Question

I have a 2D matrix, I am travelling from cell 0,0 and collect as many 1's as possible from the matrix using following:

Each cell can have values 0, 1, -1

0 means a path is present
1 means I can collect this as point
-1 means an obstruction

Below are the rules to follow:

• Start from (0,0) till end point (n-1, n-1). Move toward end point by right -> or down -> through valid cells (means cells with 0 or 1)

• After reaching (m-1, n-1) travel back to (0,0) by moving left <- or up through valid cells.

• While travelling pick all 1's and make them as empty cells (0 value)

By following this approach collect as many 1's as possible.

Example:

0 1 1
1 0 1
1 1 1

Output:
7

Explanation:

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) ->
Now reverse direction
(2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Using this path I can collect 7 ones. so result is 7.

=================

Example:

0 1 1
1 0 -1
1 1 -1

Output:
0

Explanation:

Cell (2,2) is blocked, so we cannot collect any ones 

I have come up with below in-complete code that follows step 1 means from (0,0) to end point

class Main {
    // Function to check if cell (i, j) is valid and safe to visit
    public static boolean isSafe(int[][] mat, int i, int j) {
        if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || mat[i][j] == -1) {
            return false;
        }

        return true;
    }

    // Function to collect maximum number of ones starting from
    // cell mat[i][j]
    public static int findMaximum(int[][] mat, int i, int j) {
        // return if cell (i, j) is invalid or unsafe to visit
        if (!isSafe(mat, i, j)) {
            return 0;
        }
        int max = Integer.max(findMaximum(mat, i, j + 1), findMaximum(mat, i + 1, j));
        max += mat[i][j];
        mat[i][j] = 0;// making it empty cell
        return max;
    }

    public static void main(String[] args) {
        int[][] mat = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };// 7

        System.out.println(findMaximum(mat, 0, 0));
    }
}

The program outputs 4 instead of 7. Can you please help me what is the correct way of solving this task.

Answer 1

Notice that finding a path from (i, j) to (n-1, n-1), is the same as finding a path from (n-1, n-1) to (i, j).

Also, finding a path from (0, 0) to (n-1, n-1) and then back to (0, 0) is equivalent to finding two paths from (0, 0) to (n-1, n-1), provided we don't re-count points from both paths.

To prevent this re-counting, we can find the points from both paths in lock-step as shown in this pseudo-code:

# (i1, j1) and (i2, j2) is the current location in the first and second path respectively.
def points(i1, j1, i2, j2):
    if not is_safe(i1, j1) or not is_safe(i2, j2):
        return float("-inf")
    if (i1, j1) == (i2, j2) == (n-1, n-1):
        return m[i1][j1]

    # Notice we don't double count the value if the paths cross.
    if (i1, j1) == (i2, j2):
        num_points = m[i1][j1]
    else:
        num_points = m[i1][j1] + m[i2][j2]

    return num_points + max(
        points(i1+1, j1, i2+1, j2), # Both paths go down.
        points(i1, j1+1, i2, j2+1), # Both paths go right.
        points(i1+1, j1, i2, j2+1), # First path path goes down, second goes right.
        points(i1, j1+1, i2+1, j2), # First path path goes right, second goes down.
    )

Since there will be repeated sub-computations, if we cache this function, it should give a polynomial time algorithm.

This algorithm takes O(N^3) time and will find the optimal solution even if the matrix contains points > 1.

Here is a repl with a Java implementation.