#StackBounty: #java #algorithm Collect maximum points in a grid using two traversals

Bounty: 50

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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.