Given a 2d-matrix mat[][] consisting of positive integers, the task is to find the maximum score we can reach if we have to go to cell mat[0][N – 1] starting from mat[0][0]. We have to cover the matrix in two phases:
- Phase 1: If we are at cell mat[i][j] then we can only go to cells mat[i][j + 1] or mat[i + 1][j] without changing the phase else we can go to cell mat[i – 1][j] and switch to phase 2.
- Phase 2: If we are at cell mat[i][j] then we can only go to cells mat[i][j + 1] or mat[i – 1][j].
We can not go out of bounds and the switching between phases will occur at most once.
Note: We may be able to visit the cells of column in which we switch the phase twice.
Examples:
Input: mat[][] = {
{1, 1, 1},
{1, 5, 1},
{1, 1, 1}}
Output: 15
Path: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (1, 1) -> (0, 1) -> (0, 2)
Phase 1: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1)
Phase 2: (2, 1) -> (1, 1) -> (0, 1) -> (0, 2)
Total score = 1 + 1 + 5 + 1 + 5 + 1 + 1 = 15
Input: mat[][] = {
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output: 7
Prerequisite: Maximum sum path in a matrix from top to bottom.
Approach: This problem can be solved using dynamic programming Let’s suppose we are at the cell mat[i][j] and S is the shrink factor. If its 0, then we are in phase-1 (growing phase) else we are in phase-2 (shrinking phase). Thus, S can take only two values. Set S = 1 as soon as we take a step down.
dp[i][j][S] will be defined as maximum score we can get if we get from cell mat[i][j] to mat[0][N – 1]. Now, let’s discuss the paths we can take.
Let us assume we are at cell mat[i][j].
- Case 1: When S = 0 then we have three possible paths,
- Go to cell mat[i + 1][j].
- Go to cell mat[i][j + 1].
- Go to cell mat[i – 1][j] and update S = 1.
- Case 2: When S = 1 then we have two possible paths,
- Go to cell mat[i – 1][j].
- Go to cell mat[i][j + 1].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define n 3// To store the states of the DPint dp[n][n][2];bool v[n][n][2];// Function to return the maximum// of the three integersint max(int a, int b, int c){ int m = a; if (m < b) m = b; if (m < c) m = c; return m;}// Function to return the maximum scoreint maxScore(int arr[][n], int i, int j, int s){ // Base cases if (i > n - 1 || i < 0 || j > n - 1) return 0; if (i == 0 and j == n - 1) return arr[i][j]; // If the state has already // been solved then return it if (v[i][j][s]) return dp[i][j][s]; // Marking the state as solved v[i][j][s] = 1; // Growing phase if (!s) dp[i][j][s] = arr[i][j] + max(maxScore(arr, i + 1, j, s), maxScore(arr, i, j + 1, s), maxScore(arr, i - 1, j, !s)); // Shrinking phase else dp[i][j][s] = arr[i][j] + max(maxScore(arr, i - 1, j, s), maxScore(arr, i, j + 1, s)); // Returning the solved state return dp[i][j][s];}// Driver codeint main(){ int arr[n][n] = { { 1, 1, 1 }, { 1, 5, 1 }, { 1, 1, 1 } }; cout << maxScore(arr, 0, 0, 0); return 0;} |
Java
// Java implementation of the approachclass GFG { static int n = 3; // To store the states of the DP static int[][][] dp = new int[n][n][2]; static boolean[][][] v = new boolean[n][n][2]; // Function to return the maximum // of the three integers static int max(int a, int b, int c) { int m = a; if (m < b) { m = b; } if (m < c) { m = c; } return m; }// Function to return the maximum score static int maxScore(int arr[][], int i, int j, int s) { // Base cases if (i > n - 1 || i < 0 || j > n - 1) { return 0; } if (i == 0 && j == n - 1) { return arr[i][j]; } // If the state has already // been solved then return it if (v[i][j][s]) { return dp[i][j][s]; } // Marking the state as solved v[i][j][s] = true; // Growing phase if (s != 1) { dp[i][j][s] = arr[i][j] + Math.max(maxScore(arr, i + 1, j, s), Math.max(maxScore(arr, i, j + 1, s), maxScore(arr, i - 1, j, (s==1)?0:1))); } // Shrinking phase else { dp[i][j][s] = arr[i][j] + Math.max(maxScore(arr, i - 1, j, s), maxScore(arr, i, j + 1, s)); } // Returning the solved state return dp[i][j][s]; } // Driver code public static void main(String args[]) { int arr[][] = {{1, 1, 1}, {1, 5, 1}, {1, 1, 1}}; System.out.println(maxScore(arr, 0, 0, 0)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach import numpy as np n = 3# To store the states of the DP dp = np.zeros((n,n,2)); v = np.zeros((n,n,2)); # Function to return the maximum # of the three integers def max_three(a, b, c) : m = a; if (m < b) : m = b; if (m < c) : m = c; return m; # Function to return the maximum score def maxScore(arr, i, j, s) : # Base cases if (i > n - 1 or i < 0 or j > n - 1) : return 0; if (i == 0 and j == n - 1) : return arr[i][j]; # If the state has already # been solved then return it if (v[i][j][s]) : return dp[i][j][s]; # Marking the state as solved v[i][j][s] = 1; # Growing phase if (not bool(s)) : dp[i][j][s] = arr[i][j] + max_three(maxScore(arr, i + 1, j, s), maxScore(arr, i, j + 1, s), maxScore(arr, i - 1, j, not bool(s))); # Shrinking phase else : dp[i][j][s] = arr[i][j] + max(maxScore(arr, i - 1, j, s), maxScore(arr, i, j + 1, s)); # Returning the solved state return dp[i][j][s]; # Driver code if __name__ == "__main__" : arr = [ [ 1, 1, 1 ], [ 1, 5, 1 ], [ 1, 1, 1 ] , ]; print(maxScore(arr, 0, 0, 0)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{ static int n = 3; // To store the states of the DP static int[,,] dp = new int[n,n,2]; static bool[,,] v = new bool[n,n,2]; // Function to return the maximum // of the three integers static int max(int a, int b, int c) { int m = a; if (m < b) { m = b; } if (m < c) { m = c; } return m; } // Function to return the maximum score static int maxScore(int [,]arr, int i, int j, int s) { // Base cases if (i > n - 1 || i < 0 || j > n - 1) { return 0; } if ((i == 0) && (j == (n - 1))) { return arr[i, j]; } // If the state has already // been solved then return it if (v[i, j, s]) { return dp[i, j, s]; } // Marking the state as solved v[i, j, s] = true; // Growing phase if (s != 1) { dp[i,j,s] = arr[i,j] + Math.Max(maxScore(arr, i + 1, j, s), Math.Max(maxScore(arr, i, j + 1, s), maxScore(arr, i - 1, j, (s==1)?0:1))); } // Shrinking phase else { dp[i,j,s] = arr[i,j] + Math.Max(maxScore(arr, i - 1, j, s), maxScore(arr, i, j + 1, s)); } // Returning the solved state return dp[i, j, s]; } // Driver code static public void Main () { int [,]arr = {{1, 1, 1}, {1, 5, 1}, {1, 1, 1}}; Console.WriteLine(maxScore(arr, 0, 0, 0)); }}/* This code contributed by @Tushil..... */ |
Javascript
<script> // Javascript implementation of the approach let n = 3; // To store the states of the DP let dp = new Array(n); let v = new Array(n); for(let i = 0; i < n; i++) { dp[i] = new Array(n); v[i] = new Array(n); for(let j = 0; j < n; j++) { dp[i][j] = new Array(2); v[i][j] = new Array(2); for(let k = 0; k < 2; k++) { dp[i][j][k] = 0; v[i][j][k] = 0; } } } // Function to return the maximum // of the three integers function max(a, b, c) { let m = a; if (m < b) { m = b; } if (m < c) { m = c; } return m; } // Function to return the maximum score function maxScore(arr, i, j, s) { // Base cases if (i > n - 1 || i < 0 || j > n - 1) { return 0; } if (i == 0 && j == n - 1) { return arr[i][j]; } // If the state has already // been solved then return it if (v[i][j][s]) { return dp[i][j][s]; } // Marking the state as solved v[i][j][s] = true; // Growing phase if (s != 1) { dp[i][j][s] = arr[i][j] + Math.max(maxScore(arr, i + 1, j, s), Math.max(maxScore(arr, i, j + 1, s), maxScore(arr, i - 1, j, (s==1)?0:1))); } // Shrinking phase else { dp[i][j][s] = arr[i][j] + Math.max(maxScore(arr, i - 1, j, s), maxScore(arr, i, j + 1, s)); } // Returning the solved state return dp[i][j][s]; } let arr = [[1, 1, 1], [1, 5, 1], [1, 1, 1]]; document.write(maxScore(arr, 0, 0, 0));</script> |
Output:
15
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
