# #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!!!

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