2684. Maximum Number of Moves in a Grid

[mah-shamim]

Topics: Array, Dynamic Programming, Matrix

You are given a 0-indexed m x n matrix grid consisting of positive integers.

You can start at any cell in the first column of the matrix, and traverse the grid in the following way:

• 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.

Example 1:

• Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
• Output: 3
• Explanation: We can start at the cell (0, 0) and make the following moves:
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3).
    It can be shown that it is the maximum number of moves that can be made.

Example 2:

• Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
• Output: 0
• Explanation: Starting from any cell in the first column we cannot perform any moves.

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 1 <= grid[i][j] <= 106

Hint:

1. Consider using dynamic programming to find the maximum number of moves that can be made from each cell.
2. The final answer will be the maximum value in cells of the first column.

[mah-shamim]

We can use Dynamic Programming (DP) to keep track of the maximum number of moves from each cell, starting from any cell in the first column. Here’s the step-by-step approach:

Approach:

1. Define DP Array: Let dp[row][col] represent the maximum number of moves possible starting from grid[row][col]. Initialize this with 0 for all cells.

2. Traverse the Grid:

   • Start from the last column and move backward to the first column. For each cell in column col, calculate possible moves for col-1.
   • Update dp[row][col] based on possible moves (row - 1, col + 1), (row, col + 1), and (row + 1, col + 1), only if the value of the destination cell is strictly greater than the current cell.

3. Calculate the Maximum Moves:

   • After filling out the dp table, the result will be the maximum value in the first column of dp, as it represents the maximum moves starting from any cell in the first column.

4. Edge Cases:

   • Handle cases where no moves are possible (e.g., when all paths are blocked by lower or equal values in neighboring cells).

Let's implement this solution in PHP: 2684. Maximum Number of Moves in a Grid

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function maxMoves($grid) {
    $m = count($grid);
    $n = count($grid[0]);
    
    // Initialize DP array with 0 moves for all cells
    $dp = array_fill(0, $m, array_fill(0, $n, 0));
    
    // Traverse the grid from the second-to-last column to the first
    for ($col = $n - 2; $col >= 0; $col--) {
        for ($row = 0; $row < $m; $row++) {
            // Possible moves (right-up, right, right-down)
            $moves = [
                [$row - 1, $col + 1],
                [$row, $col + 1],
                [$row + 1, $col + 1]
            ];
            
            foreach ($moves as $move) {
                list($newRow, $newCol) = $move;
                if ($newRow >= 0 && $newRow < $m && $grid[$newRow][$newCol] > $grid[$row][$col]) {
                    $dp[$row][$col] = max($dp[$row][$col], $dp[$newRow][$newCol] + 1);
                }
            }
        }
    }
    
    // Find the maximum moves starting from any cell in the first column
    $maxMoves = 0;
    for ($row = 0; $row < $m; $row++) {
        $maxMoves = max($maxMoves, $dp[$row][0]);
    }
    
    return $maxMoves;
}

// Example usage:
$grid1 = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]];
$grid2 = [[3,2,4],[2,1,9],[1,1,7]];

echo maxMoves($grid1); // Output: 3
echo "\n";
echo maxMoves($grid2); // Output: 0
?>

Explanation:

1. dp Initialization: We create a 2D array dp to store the maximum moves from each cell.
2. Loop through Columns: We iterate from the second-last column to the first, updating dp[row][col] based on possible moves to neighboring cells in the next column.
3. Maximum Moves Calculation: Finally, the maximum value in the first column of dp gives the result.

Complexity Analysis:

• Time Complexity: O(m x n) since we process each cell once.
• Space Complexity: O(m x n) for the dp array.

This solution is efficient given the constraints and will work within the provided limits.

[topugit]

Thanks to solve this problem

[mah-shamim]

Thanks