Count paths with maximum sum from top-left to bottom-right cell (Adventure in a Maze)
Given a 2D grid maze[][] of size N * N containing numbers 1, 2 or 3 where 1: means we can go Right from that cell only, 2 means we can go Down from that cell only and 3 means we can go Right and Down to both paths from that cell. We cannot go out of the maze at any time. Find the total number of paths from cell (0, 0) to cell (N – 1, N – 1). There may be many paths, but we need to select that path which contains the maximum number of Adventure. The Adventure on a path is calculated by taking the sum of all the cell values that lies in the path.
Examples:
Input: maze = {{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: 4 18
Explanation: There are total 4 paths available: 18, 17, 17, 16 out of which the Max Adventure is 18.Input: maze = {{2, 1, 3, 2, 1}, {3, 3, 1, 1, 2}, {1, 3, 2, 1, 3}, {1, 2, 3, 1, 2}, {1, 1, 3, 3, 1} }
Output: 7 23
Explanation: There are total 7 paths available out of which the max adventure is 23.
Approach:
The idea is to use Dynamic Programming to efficiently compute the total number of paths and maximum adventure in a maze. Starting from the cell (N-1, N-1), iterate through the maze in reverse, considering different movement cases (Right, Down, Both). Update the number of paths and maximum adventure at each cell based on the movement constraints. This backward traversal ensures that the answer for the right cell and the down cell which is needed for the current cell is already computed. Iterate throughout the grid to get the total number of paths and the maximum adventure.
Step-by-step algorithm:
- Iterate through the maze in reverse order (bottom-right to top-left).
- For each cell, determine the movement type (1, 2, or 3) and update the number of paths accordingly.
- If the movement is allowed (non-zero paths), update the maximum adventure based on the adjacent cells.
- Continue iterating until we reach the cell(0, 0).
- The final matrices contain the total number of paths and maximum adventure starting from the cell (0, 0).
- Return these values as the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to find the number of paths and maximum // adventure vector< int > findPathsAndMaxAdventure(vector<vector< int > >& maze) { // Defining constants and variables using ll = long long int ; ll MOD = 1e9 + 7; int n = maze.size(); vector<vector< int > > paths(n + 5, vector< int >(n + 5, 0)); vector<vector< int > > adventure(n + 5, vector< int >(n + 5, 0)); paths[n - 1][n - 1] = 0; adventure[n - 1][n - 1] = maze[n - 1][n - 1]; int i, j; // Iterating over the maze from the bottom right to the // top left for (i = n - 1; i >= 0; i--) { for (j = n - 1; j >= 0; j--) { // If it is the bottom right element, set number // of paths to 1 if (i == n - 1 && j == i) { paths[i][j] = 1; continue ; } // If the current cell is 1 if (maze[i][j] == 1) { // Number of paths is the same as the next // cell in the same row paths[i][j] = paths[i][j + 1]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j]) { adventure[i][j] = maze[i][j] + adventure[i][1 + j]; } } // If the current cell is 3 else if (maze[i][j] == 3) { // Number of paths is the sum of the number // of paths from the cell below and the next // cell in the same row paths[i][j] = (paths[i + 1][j] + paths[i][j + 1]) % MOD; // If there are paths to reach this cell // Update the maximum adventure with the // maximum of the cell below and the next // cell in the same row if (paths[i][j] != 0) { adventure[i][j] = maze[i][j] + max(adventure[i + 1][j], adventure[i][j + 1]); } } // If the current cell is 2 else if (maze[i][j] == 2) { // Number of paths is the same as the cell // below paths[i][j] = paths[i + 1][j]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j]) { adventure[i][j] = maze[i][j] + adventure[i + 1][j]; } } } } // Return the number of paths and maximum adventure as a // vector return { ( int )paths[0][0], adventure[0][0] }; } int main() { // input vector<vector< int > > maze = { { 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 } }; // Call the findPathsAndMaxAdventure function with the // provided input vector< int > result = findPathsAndMaxAdventure(maze); // Output the result cout << result[0] << " " << result[1] << endl; return 0; } |
Java
import java.util.Arrays; import java.util.List; import java.util.Vector; public class Main { // Function to find the number of paths and maximum // adventure static List<Integer> findPathsAndMaxAdventure( int [][] maze) { long MOD = 1000000007 ; int n = maze.length; int [][] paths = new int [n + 5 ][n + 5 ]; int [][] adventure = new int [n + 5 ][n + 5 ]; paths[n - 1 ][n - 1 ] = 0 ; adventure[n - 1 ][n - 1 ] = maze[n - 1 ][n - 1 ]; // Iterating over the maze from the bottom right to // the top left for ( int i = n - 1 ; i >= 0 ; i--) { for ( int j = n - 1 ; j >= 0 ; j--) { // If it is the bottom right element, set // number of paths to 1 if (i == n - 1 && j == i) { paths[i][j] = 1 ; continue ; } // If the current cell is 1 if (maze[i][j] == 1 ) { // Number of paths is the same as the // next cell in the same row paths[i][j] = paths[i][j + 1 ]; // If there are paths to reach this // cell, update the maximum adventure if (paths[i][j] != 0 ) { adventure[i][j] = maze[i][j] + adventure[i][ 1 + j]; } } // If the current cell is 3 else if (maze[i][j] == 3 ) { // Number of paths is the sum of the // number of paths from the cell below // and the next cell in the same row paths[i][j] = ( int )((paths[i + 1 ][j] + paths[i][j + 1 ]) % MOD); // If there are paths to reach this // cell, update the maximum adventure // with the maximum of the cell below // and the next cell in the same row if (paths[i][j] != 0 ) { adventure[i][j] = maze[i][j] + Math.max( adventure[i + 1 ][j], adventure[i][j + 1 ]); } } // If the current cell is 2 else if (maze[i][j] == 2 ) { // Number of paths is the same as the // cell below paths[i][j] = paths[i + 1 ][j]; // If there are paths to reach this // cell, update the maximum adventure if (paths[i][j] != 0 ) { adventure[i][j] = maze[i][j] + adventure[i + 1 ][j]; } } } } // Return the number of paths and maximum adventure // as a list return Arrays.asList(paths[ 0 ][ 0 ], adventure[ 0 ][ 0 ]); } public static void main(String[] args) { // Input int [][] maze = { { 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 } }; // Call the findPathsAndMaxAdventure function with // the provided input List<Integer> result = findPathsAndMaxAdventure(maze); // Output the result System.out.println(result.get( 0 ) + " " + result.get( 1 )); } } |
Python3
# Function to find the number of paths and maximum adventure def find_paths_and_max_adventure(maze): MOD = 10 * * 9 + 7 n = len (maze) paths = [[ 0 ] * (n + 5 ) for _ in range (n + 5 )] adventure = [[ 0 ] * (n + 5 ) for _ in range (n + 5 )] paths[n - 1 ][n - 1 ] = 0 adventure[n - 1 ][n - 1 ] = maze[n - 1 ][n - 1 ] # Iterating over the maze from the bottom right to the top left for i in range (n - 1 , - 1 , - 1 ): for j in range (n - 1 , - 1 , - 1 ): # If it is the bottom right element, set number of paths to 1 if i = = n - 1 and j = = i: paths[i][j] = 1 continue # If the current cell is 1 if maze[i][j] = = 1 : # Number of paths is the same as the next cell in the same row paths[i][j] = paths[i][j + 1 ] # If there are paths to reach this cell, update the maximum adventure if paths[i][j]: adventure[i][j] = maze[i][j] + adventure[i][j + 1 ] # If the current cell is 3 elif maze[i][j] = = 3 : # Number of paths is the sum of the number of paths from the cell below # and the next cell in the same row paths[i][j] = (paths[i + 1 ][j] + paths[i][j + 1 ]) % MOD # If there are paths to reach this cell, update the maximum adventure if paths[i][j] ! = 0 : adventure[i][j] = maze[i][j] + max (adventure[i + 1 ][j], adventure[i][j + 1 ]) # If the current cell is 2 elif maze[i][j] = = 2 : # Number of paths is the same as the cell below paths[i][j] = paths[i + 1 ][j] # If there are paths to reach this cell, update the maximum adventure if paths[i][j]: adventure[i][j] = maze[i][j] + adventure[i + 1 ][j] # Return the number of paths and maximum adventure as a vector return [ int (paths[ 0 ][ 0 ]), adventure[ 0 ][ 0 ]] # Main function def main(): # Input maze = [ [ 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 ] ] # Call the find_paths_and_max_adventure function with the provided input result = find_paths_and_max_adventure(maze) # Output the result print (result[ 0 ], result[ 1 ]) # Run the main function if the script is executed if __name__ = = "__main__" : main() # This code is contributed by shivamgupta0987654321 |
C#
using System; using System.Collections.Generic; class Program { // Function to find the number of paths and maximum adventure static List< int > FindPathsAndMaxAdventure(List<List< int >> maze) { // Defining constants and variables const int MOD = 1000000007; int n = maze.Count; List<List< int >> paths = new List<List< int >>(); List<List< int >> adventure = new List<List< int >>(); for ( int i = 0; i < n + 5; i++) { paths.Add( new List< int >( new int [n + 5])); adventure.Add( new List< int >( new int [n + 5])); } paths[n - 1][n - 1] = 0; adventure[n - 1][n - 1] = maze[n - 1][n - 1]; // Iterating over the maze from the bottom right to the top left for ( int i = n - 1; i >= 0; i--) { for ( int j = n - 1; j >= 0; j--) { // If it is the bottom right element, set number of paths to 1 if (i == n - 1 && j == i) { paths[i][j] = 1; continue ; } // If the current cell is 1 if (maze[i][j] == 1) { // Number of paths is the same as the next cell in the same row paths[i][j] = paths[i][j + 1]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j] > 0) { adventure[i][j] = maze[i][j] + adventure[i][1 + j]; } } // If the current cell is 3 else if (maze[i][j] == 3) { // Number of paths is the sum of the number of paths from the cell below // and the next cell in the same row paths[i][j] = (paths[i + 1][j] + paths[i][j + 1]) % MOD; // If there are paths to reach this cell // Update the maximum adventure with the maximum of the cell below // and the next cell in the same row if (paths[i][j] != 0) { adventure[i][j] = maze[i][j] + Math.Max(adventure[i + 1][j], adventure[i][j + 1]); } } // If the current cell is 2 else if (maze[i][j] == 2) { // Number of paths is the same as the cell below paths[i][j] = paths[i + 1][j]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j] > 0) { adventure[i][j] = maze[i][j] + adventure[i + 1][j]; } } } } // Return the number of paths and maximum adventure as a list return new List< int > { paths[0][0], adventure[0][0] }; } static void Main() { // Input List<List< int >> maze = new List<List< int >> { new List< int > { 1, 1, 3, 2, 1 }, new List< int > { 3, 2, 2, 1, 2 }, new List< int > { 1, 3, 3, 1, 3 }, new List< int > { 1, 2, 3, 1, 2 }, new List< int > { 1, 1, 1, 3, 1 } }; // Call the FindPathsAndMaxAdventure function with the provided input List< int > result = FindPathsAndMaxAdventure(maze); // Output the result Console.WriteLine(result[0] + " " + result[1]); } } |
Javascript
// Function to find the number of paths and maximum // adventure function findPathsAndMaxAdventure(maze) { const MOD = 1e9 + 7; const n = maze.length; const paths = new Array(n + 5).fill( null ).map(() => new Array(n + 5).fill(0)); const adventure = new Array(n + 5).fill( null ).map(() => new Array(n + 5).fill(0)); paths[n - 1][n - 1] = 0; adventure[n - 1][n - 1] = maze[n - 1][n - 1]; // Iterating over the maze from the bottom right to the // top left for (let i = n - 1; i >= 0; i--) { for (let j = n - 1; j >= 0; j--) { // If it is the bottom right element, set number // of paths to 1 if (i === n - 1 && j === i) { paths[i][j] = 1; continue ; } // If the current cell is 1 if (maze[i][j] === 1) { // Number of paths is the same as the next // cell in the same row paths[i][j] = paths[i][j + 1]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j]) { adventure[i][j] = maze[i][j] + adventure[i][1 + j]; } } // If the current cell is 3 else if (maze[i][j] === 3) { // Number of paths is the sum of the number // of paths from the cell below and the next // cell in the same row paths[i][j] = (paths[i + 1][j] + paths[i][j + 1]) % MOD; // If there are paths to reach this cell // Update the maximum adventure with the // maximum of the cell below and the next // cell in the same row if (paths[i][j] !== 0) { adventure[i][j] = maze[i][j] + Math.max(adventure[i + 1][j], adventure[i][j + 1]); } } // If the current cell is 2 else if (maze[i][j] === 2) { // Number of paths is the same as the cell // below paths[i][j] = paths[i + 1][j]; // If there are paths to reach this cell // Update the maximum adventure if (paths[i][j]) { adventure[i][j] = maze[i][j] + adventure[i + 1][j]; } } } } // Return the number of paths and maximum adventure as a // array return [paths[0][0], adventure[0][0]]; } // input const maze = [ [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] ]; // Call the findPathsAndMaxAdventure function with the // provided input const result = findPathsAndMaxAdventure(maze); // Output the result console.log(result[0] + " " + result[1]); |
4 18
Time Complexity: O(N^2), where N is the number of rows or columns in the input maze[][].
Auxiliary Space: O(N^2)