title: Collect maximum points in a grid using two traversals
body: <p>I have a 2D matrix, I am travelling from cell <code>0,0</code> and collect as many 1's as possible from the matrix using following:</p>
  <p>Each cell can have values <code>0</code>, <code>1</code>, <code>-1</code></p>
  <pre><code>0 means a path is present
  1 means I can collect this as point
  -1 means an obstruction
  </code></pre>
  <p>Below are the rules to follow:</p>
  <ul>
  <li><p>Start from (0,0) till end point (n-1, n-1). Move toward end point by
  right -&gt; or down -&gt; through valid cells (means cells with 0 or 1)</p>
  </li>
  <li><p>After reaching (m-1, n-1) travel back to (0,0) by moving left &lt;- or up
  through valid cells.</p>
  </li>
  <li><p>While travelling pick all 1's and make them as empty cells (0 value)</p>
  </li>
  </ul>
  <p>By following this approach collect as many 1's as possible.</p>
  <pre><code>Example:
  
  0 1 1
  1 0 1
  1 1 1
  
  Output:
  7
  
  Explanation:
  
  (0,0) -&gt; (0,1) -&gt; (0,2) -&gt; (1,2) -&gt; (2,2) -&gt;
  Now reverse direction
  (2,2) -&gt; (2,1) -&gt; (2,0) -&gt; (1,0) -&gt; (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 
  </code></pre>
  <p>I have come up with below in-complete code that follows step 1 means from (0,0) to end point</p>
  <pre><code>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 &lt; 0 || i &gt;= mat.length || j &lt; 0 || j &gt;= 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));
      }
  }
  </code></pre>
  <p>The program outputs <code>4</code> instead of <code>7</code>. Can you please help me what is the correct way of solving this task.</p>