content: package codingquestions.leetcode;
  
  /**
   * 2684. Maximum Number of Moves in a Grid
   * Solved
   * Medium
   * Topics
   * Companies
   * Hint
   * You are given a 0-indexed m x n matrix grid consisting of positive integers.
   * <p>
   * You can start at any cell in the first column of the matrix, and traverse the grid in the following way:
   * <p>
   * From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell.
   * Return the maximum number of moves that you can perform.
   **/
  public class MaximumNumberofMovesinaGrid {
      public int maxMoves(int[][] grid) {
          // Get dimensions of the grid
          int m = grid.length;    // number of rows
          int n = grid[0].length; // number of columns
  
          // res will store the rightmost column we can reach
          int res = 0;
  
          // dp array stores the maximum number of moves possible to reach each cell
          // in the current column we're processing
          int[] dp = new int[m];
  
          // Iterate through each column from left to right (starting from column 1)
          for (int j = 1; j < n; j++) {
              // leftTop keeps track of the dp value from the cell above-left
              int leftTop = 0;
              // found indicates if we can reach any cell in current column
              boolean found = false;
  
              // Iterate through each row in current column
              for (int i = 0; i < m; i++) {
                  // cur will store the maximum moves to reach current cell
                  int cur = -1;
                  // Store dp[i] for next iteration's leftTop
                  int nxtLeftTop = dp[i];
  
                  // Check move from top-left cell (if valid)
                  if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {
                      cur = Math.max(cur, leftTop + 1);
                  }
  
                  // Check move from direct left cell (if valid)
                  if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {
                      cur = Math.max(cur, dp[i] + 1);
                  }
  
                  // Check move from bottom-left cell (if valid)
                  if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {
                      cur = Math.max(cur, dp[i + 1] + 1);
                  }
  
                  // Update dp array for current cell
                  dp[i] = cur;
                  // Update found flag if we can reach current cell
                  found = found || (dp[i] != -1);
                  // Update leftTop for next row's iteration
                  leftTop = nxtLeftTop;
              }
  
              // If we can't reach any cell in current column, break
              if (!found) break;
              // Update result to current column if we can reach it
              res = j;
          }
  
          // Return the maximum number of moves possible
          return res;
      }
  }
  