Table of Contents
Problem Statement
We are given a matrix of size “n x m”, and we need to collect maximum points in a grid using two traversals. If we are standing at cell i,j then we have three options to go to cell i+1, j or i+1, j-1or i+1, j+1. That is we will move to the next row in the down direction from the current cell, and to the current column, or to adjacent columns. We need to start from the top left corner and go to the left bottom corner. For the second traversal, we need to move from the top right corner to the bottom right corner.
Example
Size of matrix = 3 x 3 Matrix 10 2 20 9 10 5 10 100 20
75
Explanation: First traversal moves are from 10->10->10, making a total of 30 points.
Second traversal moves are 20->5->20, thus total is 20+5+20 = 45 points. Here we couldn’t choose 100 since then we would not have been able to reach our destinations in both the cases (First and second traversal). Thus the maximum points we could’ve collected is 75.
Algorithm to collect maximum points in a grid using two traversals
Naive Approach
We can use a recursive approach, where first we find the maximum points that can be collected using the first traversal. While first traversal we should’ve marked the cells which have been used as a path for the first traversal. Now when we reach our second destination that is the right bottom corner. We find the total sum and update the answer accordingly. So, doing this we would have gone through all the possible combinations of first and second traversal. But since this solution has exponential time complexity, it is not suitable.
Efficient Approach
We run first and second traversals concurrently and use dynamic programming. So, we will be starting from the top left and top right corners. And keep on moving to the next row in a downward direction. But now since we are running traversals concurrently. We have a total of 9 combinations to choose from (3 for first traversal and 3 for the second traversal, making it 3*3 = 9 combinations).
Now, since subproblems are overlapping(that is we will be solving the same subproblem multiple times). Thus it is advisable to store the result of subproblems which will reduce our exponential time complexity to polynomial time complexity.
Code
C++ code for collect maximum points in a grid using two traversals problem
#include<bits/stdc++.h>
using namespace std;
int dir[3] = {-1, 0, 1};
bool isValid(int x, int y1, int y2, int rowSize, int colSize){
return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
}
int collectMaxPointsInGridUsingTwoTraversals(vector<vector<int>> &matrix, vector<vector<vector<int>>> &dp, int x, int y1, int y2, int rowSize, int colSize)
{
if(!isValid(x, y1, y2, rowSize, colSize))
return INT_MIN;
if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
if (x == rowSize-1)
return INT_MIN;
if (dp[x][y1][y2] != -1)
return dp[x][y1][y2];
int ans = INT_MIN;
int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
for(int i = 0; i < 3; i++){
for(int j=0;j<3;j++){
ans = max(ans, currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize));
}
}
return (dp[x][y1][y2] = ans);
}
int main()
{
int rowSize, colSize;
cin>>rowSize>>colSize;
vector<vector<int>> matrix(rowSize, vector<int>(colSize));
vector<vector<vector<int>>> dp(rowSize, vector<vector<int>>(colSize, vector<int>(colSize, -1)));
for(int i=0;i<rowSize;i++){
for(int j=0;j<colSize;j++)
cin>>matrix[i][j];
}
cout << "Maximum collection is " <<collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
return 0;
}
3 3 10 1 20 5 10 5 10 100 20
Maximum collection is 75
Java code for collect maximum points in a grid using two traversals problem
import java.util.*;
class Main{
static int dir[] = {-1, 0, 1};
static boolean isValid(int x, int y1, int y2, int rowSize, int colSize){
return (x>=0 && x<rowSize && y1>=0 && y1<colSize && y2>=0 && y2<colSize);
}
static int collectMaxPointsInGridUsingTwoTraversals(int[][] matrix, int[][][] dp, int x, int y1, int y2, int rowSize, int colSize)
{
if(!isValid(x, y1, y2, rowSize, colSize))
return Integer.MIN_VALUE;
if (x == rowSize-1 && y1 == 0 && y2 == colSize-1)
return (y1 == y2)? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
if (x == rowSize-1)
return Integer.MIN_VALUE;
if (dp[x][y1][y2] != -1)
return dp[x][y1][y2];
int ans = Integer.MIN_VALUE;
int currentVal = (y1 == y2) ? matrix[x][y1]: (matrix[x][y1] + matrix[x][y2]);
for(int i = 0; i < 3; i++){
for(int j=0;j<3;j++){
int tmp = currentVal + collectMaxPointsInGridUsingTwoTraversals(matrix, dp, x+1, y1+dir[i], y2+dir[j], rowSize, colSize);
ans = Math.max(ans, tmp);
}
}
return (dp[x][y1][y2] = ans);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int rowSize = sc.nextInt();
int colSize = sc.nextInt();
int matrix[][] = new int[rowSize][colSize];
int dp[][][] = new int[rowSize][colSize][colSize];
for(int i=0;i<rowSize;i++){
for(int j=0;j<colSize;j++){
matrix[i][j] = sc.nextInt();
for(int k=0;k<colSize;k++)
dp[i][j][k] = -1;
}
}
int answer = collectMaxPointsInGridUsingTwoTraversals(matrix, dp, 0,0,colSize-1, rowSize, colSize);
System.out.println("Maximum collection is "+answer);
}
}
3 3 10 1 20 5 10 5 10 100 20
Maximum collection is 75
Complexity Analysis
Time Complexity
O(NM^2), since there are total N*M^2 states and since at max we can travel all the states. We have a polynomial-time complexity for this algorithm.
Space Complexity
O(NM^2), since there are total N*M^2 states and since at max we can travel all the states. Here DP array has 3 dimensions of size N x M x M, thus polynomial space complexity is achieved.