Scribd
Upload
2 views2 pages

Maximum Moves in Grid Problem

The document presents a C++ program that solves a maximization problem using dynamic programming to find the maximum number of moves in a grid. It initializes a DP array to track moves from the first column and iterates through the grid to update possible moves based on adjacent cells. The program includes two examples demonstrating the functionality, with outputs indicating the maximum moves for each grid configuration.

Uploaded by

mainhoondon123654789
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views2 pages

Maximum Moves in Grid Problem

The document presents a C++ program that solves a maximization problem using dynamic programming to find the maximum number of moves in a grid. It initializes a DP array to track moves from the first column and iterates through the grid to update possible moves based on adjacent cells. The program includes two examples demonstrating the functionality, with outputs indicating the maximum moves for each grid configuration.

Uploaded by

mainhoondon123654789
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Maximization Problem

#include <iostream>
#include <vector>

using namespace std;

int maxMoves(vector<vector<int>>& grid) {


int m = [Link]();
int n = grid[0].size();

// Created a 2D DP array to store the maximum number of moves for each cell.
vector<vector<int>> dp(m, vector<int>(n, 0));

// Initialized the DP array with 1, as we can always start from a cell in the first column.
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}

// Iterated through the matrix to update the DP array.


for (int col = 1; col < n; col++) {
for (int row = 0; row < m; row++) {
// Initialize the maximum moves to 0 for the current cell.
int max_moves = 0;

// Checked the three possible moves to the right and updated max_moves accordingly.
for (int dr = -1; dr <= 1; dr++) {
int new_row = row + dr;
if (new_row >= 0 && new_row < m && grid[new_row][col] > grid[row][col - 1]) {
max_moves = max(max_moves, dp[new_row][col - 1] + 1);
}
}

dp[row][col] = max(max_moves, dp[row][col]);


}
}

// The maximum moves is the maximum value in the last column of the DP array.
int max_moves = 0;
for (int i = 0; i < m; i++) {
max_moves = max(max_moves, dp[i][n - 1]);
}
return max_moves;
}

int main() {
// Example 1
vector<vector<int>> grid1 = {{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}};
cout << maxMoves(grid1) << endl; // Output: 3

// Example 2
vector<vector<int>> grid2 = {{3, 2, 4}, {2, 1, 9}, {1, 1, 7}};
cout << maxMoves(grid2) << endl; // Output: 0

return 0;
}
Output

You might also like