Given a maze which is a N * N grid grid[][]. Every cell of the maze contains either the number 1, 2 or 3 which defines the moves as:
- If grid[i][j] = 1 then the only valid move is grid[i][j + 1].
- If grid[i][j] = 2 then the only valid move is grid[i + 1][j].
- If grid[i][j] = 3 then the valid moves are grid[i][j + 1] and grid[i + 1][j].
Now, the task is to find the count of all the paths from grid[0][0] to grid[N – 1][N – 1] and the maximum possible sum among all the paths i.e. when all the values at the visited cells are added to the sum.
Examples:
Input: grid[][] = {
{3, 2},
{3, 1}}
Output:
Total paths: 2
Maximum sum: 7
The two valid paths are
(0, 0) -> (0, 1) -> (1, 1) with sum as 3 + 2 + 1 = 6
and (0, 0) -> (1, 0) -> (1, 1) with sum as 3 + 3 + 1 = 7
Input: grid[][] = {
{1, 1, 3, 2, 1},
{3, 2, 2, 1, 2},
{1, 3, 3, 1, 3},
{1, 2, 3, 1, 2},
{1, 1, 1, 3, 1}}
Output:
Total paths: 4
Maximum sum: 18
Approach: This problem can be solved using dynamic programming.
To count the number of paths, create a dp[][] array where dp[i][j] will store the count of paths from grid[i][j] to grid[N – 1][N – 1] and the recurrence relation will be,
- If grid[i][j] = 1 then dp[i][j] = dp[i][j + 1].
- If grid[i][j] = 2 then dp[i][j] = dp[i + 1][j].
- If grid[i][j] = 1 then dp[i][j] = dp[i][j + 1] + dp[i + 1][j].
and the termination condition will be when source and destination are same i.e. dp[N – 1][N – 1] = 1.
Now, to find the maximum sum path, another dp[][] array can be created where dp[i][j] will store the maximum sum of the path from grid[i][j] to grid[N – 1][N – 1] and the recurrence relation will be,
- If grid[i][j] = 1 then dp[i][j] = grid[i][j] + dp[i][j + 1].
- If grid[i][j] = 2 then dp[i][j] = grid[i][j] + dp[i + 1][j].
- If grid[i][j] = 1 then dp[i][j] = grid[i][j] + max(dp[i][j + 1] + dp[i + 1][j]).
and the termination condition will again be when source and destination are same i.e. dp[N – 1][N – 1] = grid[N – 1][N – 1].
C++
// C++ implementation of the approach#include<bits/stdc++.h>#define COL 5#define ROW 5using namespace std;// Recursive function to return the total// paths from grid[i][j] to grid[n - 1][n - 1]int totalPaths(int i, int j, int n, int grid[][COL], int dp[][COL]){ // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = totalPaths(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = totalPaths(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = totalPaths(i, j + 1, n, grid, dp) + totalPaths(i + 1, j, n, grid, dp); } return dp[i][j];}// Recursive function to return the maximum// sum along the path from grid[i][j] to grid[n - 1][n - 1]int maxSumPath(int i, int j, int n, int grid[ROW][COL], int dp[ROW][COL]){ // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = grid[i][j] + maxSumPath(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = grid[i][j] + maxSumPath(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = grid[i][j] + max(maxSumPath(i, j + 1, n, grid, dp), maxSumPath(i + 1, j, n, grid, dp)); } return dp[i][j];}// Driver codeint main(){ int grid[ROW][COL] = { { 1, 1, 3, 2, 1 }, { 3, 2, 2, 1, 2 }, { 1, 3, 3, 1, 3 }, { 1, 2, 3, 1, 2 }, { 1, 1, 1, 3, 1 } }; int n = ROW; // Fill the dp[][] array with -1 int dp[ROW][COL]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) dp[i][j] = -1; } // When source and destination are same // then there is only 1 path dp[n - 1][n - 1] = 1; // Print the count of paths from // grid[0][0] to grid[n - 1][n - 1] cout<<"Total paths: " << totalPaths(0, 0, n, grid, dp) << endl; // Fill the dp[][] array again with -1 //for (int i = 0; i < n; i++) // Arrays.fill(dp[i], -1); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) dp[i][j] = -1; } // When source and destination are same // then the sum is grid[n - 1][n - 1] dp[n - 1][n - 1] = grid[n - 1][n - 1]; // Print the maximum sum among all the paths // from grid[0][0] to grid[n - 1][n - 1] cout<< "Maximum sum: " << maxSumPath(0, 0, n, grid, dp)<<endl; return 0;}// This code is contributed by Rajput-Ji |
Java
// Java implementation of the approachimport java.util.Arrays;class GFG { // Recursive function to return the total // paths from grid[i][j] to grid[n - 1][n - 1] static int totalPaths(int i, int j, int n, int grid[][], int dp[][]) { // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = totalPaths(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = totalPaths(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = totalPaths(i, j + 1, n, grid, dp) + totalPaths(i + 1, j, n, grid, dp); } return dp[i][j]; } // Recursive function to return the maximum // sum along the path from grid[i][j] to grid[n - 1][n - 1] static int maxSumPath(int i, int j, int n, int grid[][], int dp[][]) { // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = grid[i][j] + maxSumPath(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = grid[i][j] + maxSumPath(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = grid[i][j] + Math.max(maxSumPath(i, j + 1, n, grid, dp), maxSumPath(i + 1, j, n, grid, dp)); } return dp[i][j]; } // Driver code public static void main(String[] args) { int grid[][] = { { 1, 1, 3, 2, 1 }, { 3, 2, 2, 1, 2 }, { 1, 3, 3, 1, 3 }, { 1, 2, 3, 1, 2 }, { 1, 1, 1, 3, 1 } }; int n = grid.length; // Fill the dp[][] array with -1 int dp[][] = new int[n][n]; for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1); // When source and destination are same // then there is only 1 path dp[n - 1][n - 1] = 1; // Print the count of paths from // grid[0][0] to grid[n - 1][n - 1] System.out.println("Total paths: " + totalPaths(0, 0, n, grid, dp)); // Fill the dp[][] array again with -1 for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1); // When source and destination are same // then the sum is grid[n - 1][n - 1] dp[n - 1][n - 1] = grid[n - 1][n - 1]; // Print the maximum sum among all the paths // from grid[0][0] to grid[n - 1][n - 1] System.out.println("Maximum sum: " + maxSumPath(0, 0, n, grid, dp)); }} |
Python3
# Python3 implementation of the approach # Recursive function to return the total # paths from grid[i][j] to grid[n - 1][n - 1] def totalPaths(i, j, n, grid, dp): # Out of bounds if (i < 0 or j < 0 or i >= n or j >= n): return 0 # If the current state # hasn't been solved before if (dp[i][j] == -1): # Only valid move is right if (grid[i][j] == 1): dp[i][j] = totalPaths(i, j + 1, n, grid, dp) # Only valid move is down elif (grid[i][j] == 2): dp[i][j] = totalPaths(i + 1, j, n, grid, dp) # Right and down, both are valid moves else: dp[i][j] = totalPaths(i, j + 1, n, grid, dp) +\ totalPaths(i + 1, j, n, grid, dp) return dp[i][j] # Recursive function to return the maximum # sum along the path from grid[i,j] to grid[n - 1,n - 1] def maxSumPath(i, j, n, grid, dp): # Out of bounds if (i < 0 or j < 0 or i >= n or j >= n): return 0 # If the current state # hasn't been solved before if (dp[i][j] == -1): # Only valid move is right if (grid[i][j] == 1): dp[i][j] = grid[i][j] + \ maxSumPath(i, j + 1, n, grid, dp) # Only valid move is down elif (grid[i][j] == 2): dp[i][j] = grid[i][j] + \ maxSumPath(i + 1, j, n, grid, dp) # Right and down, both are valid moves else: dp[i][j] = grid[i][j] + \ max(maxSumPath(i, j + 1, n, grid, dp), maxSumPath(i + 1, j, n, grid, dp)) return dp[i][j] # Driver code if __name__ == '__main__': grid = [[ 1, 1, 3, 2, 1 ], [ 3, 2, 2, 1, 2 ], [ 1, 3, 3, 1, 3 ], [ 1, 2, 3, 1, 2 ], [ 1, 1, 1, 3, 1 ]] n = len(grid[0]) # Fill the dp[n][n] array with -1 dp= [[-1] * n] * n # When source and destination are same # then there is only 1 path dp[n - 1][n - 1] = 1 # Print the count of paths from # grid[0,0] to grid[n - 1][n - 1] print("Total paths:", totalPaths(0, 0, n, grid, dp)) # Fill the dp[n][n] array again with -1 dp= [[-1] * n] * n # When source and destination are same # then the sum is grid[n - 1][n - 1] dp[n - 1][n - 1] = grid[n - 1][n - 1] # Print the maximum sum among all the paths # from grid[0,0] to grid[n - 1][n - 1] print("Maximum sum:", maxSumPath(0, 0, n, grid, dp)) # This code is contributed by ashutosh450 |
C#
// C# implementation of the approachusing System;class GFG {// Recursive function to return the total// paths from grid[i][j] to grid[n - 1][n - 1]static int totalPaths(int i, int j, int n, int [,]grid, int [,]dp){ // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state // hasn't been solved before if (dp[i, j] == -1) { // Only valid move is right if (grid[i, j] == 1) dp[i, j] = totalPaths(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i, j] == 2) dp[i, j] = totalPaths(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i, j] = totalPaths(i, j + 1, n, grid, dp) + totalPaths(i + 1, j, n, grid, dp); } return dp[i, j];}// Recursive function to return the maximum// sum along the path from grid[i,j] to grid[n - 1,n - 1]static int maxSumPath(int i, int j, int n, int [,]grid, int [,]dp){ // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state // hasn't been solved before if (dp[i, j] == -1) { // Only valid move is right if (grid[i, j] == 1) dp[i, j] = grid[i, j] + maxSumPath(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i,j] == 2) dp[i, j] = grid[i, j] + maxSumPath(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i, j] = grid[i, j] + Math.Max(maxSumPath(i, j + 1, n, grid, dp), maxSumPath(i + 1, j, n, grid, dp)); } return dp[i, j];}// Driver codepublic static void Main(String[] args){ int [,]grid = { { 1, 1, 3, 2, 1 }, { 3, 2, 2, 1, 2 }, { 1, 3, 3, 1, 3 }, { 1, 2, 3, 1, 2 }, { 1, 1, 1, 3, 1 } }; int n = grid.GetLength(0); // Fill the dp[,] array with -1 int [,]dp = new int[n, n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i, j] = -1; // When source and destination are same // then there is only 1 path dp[n - 1, n - 1] = 1; // Print the count of paths from // grid[0,0] to grid[n - 1,n - 1] Console.WriteLine("Total paths: " + totalPaths(0, 0, n, grid, dp)); // Fill the dp[,] array again with -1 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i, j] = -1; // When source and destination are same // then the sum is grid[n - 1,n - 1] dp[n - 1, n - 1] = grid[n - 1, n - 1]; // Print the maximum sum among all the paths // from grid[0,0] to grid[n - 1,n - 1] Console.WriteLine("Maximum sum: " + maxSumPath(0, 0, n, grid, dp));}}// This code is contributed by Princi Singh |
Javascript
<script> // Javascript implementation of the approach // Recursive function to return the total // paths from grid[i][j] to grid[n - 1][n - 1] function totalPaths(i, j, n, grid, dp) { // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = totalPaths(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = totalPaths(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = totalPaths(i, j + 1, n, grid, dp) + totalPaths(i + 1, j, n, grid, dp); } return dp[i][j]; } // Recursive function to return the maximum // sum along the path from grid[i][j] to grid[n - 1][n - 1] function maxSumPath(i, j, n, grid, dp) { // Out of bounds if (i < 0 || j < 0 || i >= n || j >= n) return 0; // If the current state hasn't been solved before if (dp[i][j] == -1) { // Only valid move is right if (grid[i][j] == 1) dp[i][j] = grid[i][j] + maxSumPath(i, j + 1, n, grid, dp); // Only valid move is down else if (grid[i][j] == 2) dp[i][j] = grid[i][j] + maxSumPath(i + 1, j, n, grid, dp); // Right and down, both are valid moves else dp[i][j] = grid[i][j] + Math.max(maxSumPath(i, j + 1, n, grid, dp), maxSumPath(i + 1, j, n, grid, dp)); } return dp[i][j]; } let grid = [ [ 1, 1, 3, 2, 1 ], [ 3, 2, 2, 1, 2 ], [ 1, 3, 3, 1, 3 ], [ 1, 2, 3, 1, 2 ], [ 1, 1, 1, 3, 1 ] ]; let n = grid.length; // Fill the dp[][] array with -1 let dp = new Array(n); for (let i = 0; i < n; i++) { dp[i] = new Array(n); for (let j = 0; j < n; j++) { dp[i][j] = -1; } } // When source and destination are same // then there is only 1 path dp[n - 1][n - 1] = 1; // Print the count of paths from // grid[0][0] to grid[n - 1][n - 1] document.write("Total paths: " + totalPaths(0, 0, n, grid, dp) + "</br>"); // Fill the dp[][] array again with -1 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { dp[i][j] = -1; } } // When source and destination are same // then the sum is grid[n - 1][n - 1] dp[n - 1][n - 1] = grid[n - 1][n - 1]; // Print the maximum sum among all the paths // from grid[0][0] to grid[n - 1][n - 1] document.write("Maximum sum: " + maxSumPath(0, 0, n, grid, dp)); // This code is contributed by mukesh07.</script> |
Output:
Total paths: 4 Maximum sum: 18
Time complexity: O(n2)
Space complexity: O(n2)
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!
