Maximum Ways to Cross the field
Given a field in the shape of a (m x n) grid, with a car initially positioned at the coordinates [row, column]. You have the ability to move the car to one of the four adjacent cells in the field, possibly crossing the field’s boundaries. You are limited to a maximum of maxlocomote moves for the car, the task is to find the number of paths that allow the car to move out of the field’s boundary. Since the answer can be very large, return it modulo 10^9 + 7.
In summary, you need to calculate the number of valid paths that the car can take to exit the field, considering the given constraints on grid dimensions, starting position, and maximum allowed moves.
Examples:
Input : m = 4, n = 8, maxlocomote = 5, Row = 1, Column = 2
Output : 125
Explanation : The Car can at max move 125 different paths to exit out the field.Input : m = 3, n = 3, maxlocomote = 3, Row = 1, Column = 1
Output : 20
Explanation : The Car can at max move20 different paths to exit out the field.
Approach: Follow the steps to solve the problem:
- Function Signature:
- m: The number of rows in the grid.
- n: The number of columns in the grid.
- maxlocomote: The maximum number of moves allowed.
- Row: The starting row.
- Column: The starting column.
- Initialize DP Array:
- dp[i][j][k] will store the number of ways to reach the boundary, starting from position (i, j) with k moves left.
- Base Cases:
- If the starting position is outside the grid (Row >= m, Column >= n, Row < 0, Column < 0), there is only one way to stay outside the grid: return 1.
- If maxlocomote is 0, no more moves are allowed, so return 0.
- Recursive Calls:
- The function solver recursively calls itself, considering four possible directions: up, down, left, and right. It tries to explore all possible paths within the maximum locomotive allowed.
- The total number of ways is the sum of the number of ways after moving in each direction.
- Memoization:
- Before making a recursive call, the function checks if the result for the current state has already been computed. If so, it returns the stored result.
- Modulus Operation:
- To prevent integer overflow, the number of ways is taken modulo 1000000007.
- Return Value:
- The function findPaths initializes the DP array and calls solver with the given parameters. It returns the result obtained.
Below is the implementation of above approach:
C++14
#include <bits/stdc++.h> using namespace std; // Define a 3D array to store results of subproblems int dp[51][51][51]; // Recursive function to find the number of ways to reach // the boundary long long solver( int m, int n, int maxlocomote, int Row, int Column) { // Base case: If the current position is outside the // grid, return 1 (one way to stay outside the grid) if (Row == m or Column == n or Row < 0 or Column < 0) { return 1; } // Base case: If no more moves are allowed, return 0 (no // ways to move further) if (maxlocomote == 0) { return 0; } // If the result for current state is already // calculated, return it if (dp[Row][Column][maxlocomote] != -1) { return dp[Row][Column][maxlocomote]; } // Initialize a variable to store the total number of // ways long long ways = 0; // Recur in four possible directions: up, down, left, // and right ways += solver(m, n, maxlocomote - 1, Row - 1, Column); // Up ways += solver(m, n, maxlocomote - 1, Row + 1, Column); // Down ways += solver(m, n, maxlocomote - 1, Row, Column - 1); // Left ways += solver(m, n, maxlocomote - 1, Row, Column + 1); // Right // Store the result and return return dp[Row][Column][maxlocomote] = ways % 1000000007; } // Function to find the number of ways to reach the boundary int findPaths( int m, int n, int maxlocomote, int Row, int Column) { // Initialize the DP array with -1 for memoization memset (dp, -1, sizeof (dp)); // Call the solver function and return the result return solver(m, n, maxlocomote, Row, Column); } int main() { // Example usage int m = 3, n = 3, maxlocomote = 3, Row = 1, Column = 1; cout << findPaths(m, n, maxlocomote, Row, Column); } |
Java
import java.util.Arrays; public class BoundaryWays { // Define a 3D array to store results of subproblems static long [][][] dp = new long [ 51 ][ 51 ][ 51 ]; // Recursive function to find the number of ways to reach // the boundary static long solver( int m, int n, int maxlocomote, int Row, int Column) { // Base case: If the current position is outside the // grid, return 1 (one way to stay outside the grid) if (Row == m || Column == n || Row < 0 || Column < 0 ) { return 1 ; } // Base case: If no more moves are allowed, return 0 (no // ways to move further) if (maxlocomote == 0 ) { return 0 ; } // If the result for the current state is already // calculated, return it if (dp[Row][Column][maxlocomote] != - 1 ) { return dp[Row][Column][maxlocomote]; } // Initialize a variable to store the total number of // ways long ways = 0 ; // Recur in four possible directions: up, down, left, // and right ways += solver(m, n, maxlocomote - 1 , Row - 1 , Column); // Up ways += solver(m, n, maxlocomote - 1 , Row + 1 , Column); // Down ways += solver(m, n, maxlocomote - 1 , Row, Column - 1 ); // Left ways += solver(m, n, maxlocomote - 1 , Row, Column + 1 ); // Right // Store the result and return return dp[Row][Column][maxlocomote] = ways % 1000000007 ; } // Function to find the number of ways to reach the boundary static int findPaths( int m, int n, int maxlocomote, int Row, int Column) { // Initialize the DP array with -1 for memoization for ( long [][] matrix : dp) { for ( long [] row : matrix) { Arrays.fill(row, - 1 ); } } // Call the solver function and return the result return ( int ) solver(m, n, maxlocomote, Row, Column); } public static void main(String[] args) { // Example usage int m = 3 , n = 3 , maxlocomote = 3 , Row = 1 , Column = 1 ; System.out.println(findPaths(m, n, maxlocomote, Row, Column)); } } // This code is contributed by shivamgupta0987654321 |
Python3
# Define a 3D array to store results of subproblems dp = [[[ - 1 for _ in range ( 51 )] for _ in range ( 51 )] for _ in range ( 51 )] # Recursive function to find the number of ways to reach # the boundary def solver(m, n, maxlocomote, Row, Column): # Base case: If the current position is outside the # grid, return 1 (one way to stay outside the grid) if Row = = m or Column = = n or Row < 0 or Column < 0 : return 1 # Base case: If no more moves are allowed, return 0 (no # ways to move further) if maxlocomote = = 0 : return 0 # If the result for the current state is already # calculated, return it if dp[Row][Column][maxlocomote] ! = - 1 : return dp[Row][Column][maxlocomote] # Initialize a variable to store the total number of # ways ways = 0 # Recur in four possible directions: up, down, left, # and right ways + = solver(m, n, maxlocomote - 1 , Row - 1 , Column) # Up ways + = solver(m, n, maxlocomote - 1 , Row + 1 , Column) # Down ways + = solver(m, n, maxlocomote - 1 , Row, Column - 1 ) # Left ways + = solver(m, n, maxlocomote - 1 , Row, Column + 1 ) # Right # Store the result and return dp[Row][Column][maxlocomote] = ways % 1000000007 return dp[Row][Column][maxlocomote] # Function to find the number of ways to reach the boundary def find_paths(m, n, maxlocomote, Row, Column): # Initialize the DP array with -1 for memoization global dp dp = [[[ - 1 for _ in range ( 51 )] for _ in range ( 51 )] for _ in range ( 51 )] # Call the solver function and return the result return solver(m, n, maxlocomote, Row, Column) # Example usage if __name__ = = "__main__" : m, n, maxlocomote, Row, Column = 3 , 3 , 3 , 1 , 1 print (find_paths(m, n, maxlocomote, Row, Column)) |
C#
using System; class Program { // Define a 3D array to store results of subproblems static long [,,] dp = new long [51, 51, 51]; // Recursive function to find the number of ways to reach // the boundary static long Solver( int m, int n, int maxlocomote, int row, int column) { // Base case: If the current position is outside the // grid, return 1 (one way to stay outside the grid) if (row == m || column == n || row < 0 || column < 0) { return 1; } // Base case: If no more moves are allowed, return 0 (no // ways to move further) if (maxlocomote == 0) { return 0; } // If the result for the current state is already // calculated, return it if (dp[row, column, maxlocomote] != 0) { return dp[row, column, maxlocomote]; } // Initialize a variable to store the total number of ways long ways = 0; // Recur in four possible directions: up, down, left, // and right ways += Solver(m, n, maxlocomote - 1, row - 1, column); // Up ways += Solver(m, n, maxlocomote - 1, row + 1, column); // Down ways += Solver(m, n, maxlocomote - 1, row, column - 1); // Left ways += Solver(m, n, maxlocomote - 1, row, column + 1); // Right // Store the result and return dp[row, column, maxlocomote] = ways % 1000000007; return dp[row, column, maxlocomote]; } // Function to find the number of ways to reach the boundary static int FindPaths( int m, int n, int maxlocomote, int row, int column) { // Initialize the DP array with 0 for memoization for ( int i = 0; i < 51; i++) { for ( int j = 0; j < 51; j++) { for ( int k = 0; k < 51; k++) { dp[i, j, k] = 0; } } } // Call the solver function and return the result return ( int )Solver(m, n, maxlocomote, row, column); } static void Main() { // Example usage int m = 3, n = 3, maxlocomote = 3, row = 1, column = 1; Console.WriteLine(FindPaths(m, n, maxlocomote, row, column)); } } |
Javascript
// Define a 3D array to store results of subproblems let dp = new Array(51).fill( null ).map(() => new Array(51).fill( null ).map(() => new Array(51).fill(-1)) ); // Recursive function to find the number of ways to reach the boundary function solver(m, n, maxlocomote, Row, Column) { // Base case: If the current position is outside the grid, return 1 (one way to stay outside the grid) if (Row === m || Column === n || Row < 0 || Column < 0) { return 1; } // Base case: If no more moves are allowed, return 0 (no ways to move further) if (maxlocomote === 0) { return 0; } // If the result for the current state is already calculated, return it if (dp[Row][Column][maxlocomote] !== -1) { return dp[Row][Column][maxlocomote]; } // Initialize a variable to store the total number of ways let ways = 0; // Recur in four possible directions: up, down, left, and right ways += solver(m, n, maxlocomote - 1, Row - 1, Column); // Up ways += solver(m, n, maxlocomote - 1, Row + 1, Column); // Down ways += solver(m, n, maxlocomote - 1, Row, Column - 1); // Left ways += solver(m, n, maxlocomote - 1, Row, Column + 1); // Right // Store the result and return return (dp[Row][Column][maxlocomote] = ways % 1000000007); } // Function to find the number of ways to reach the boundary function findPaths(m, n, maxlocomote, Row, Column) { // Initialize the DP array with -1 for memoization dp = new Array(51).fill( null ).map(() => new Array(51).fill( null ).map(() => new Array(51).fill(-1)) ); // Call the solver function and return the result return solver(m, n, maxlocomote, Row, Column); } // Example usage const m = 3, n = 3, maxlocomote = 3, Row = 1, Column = 1; console.log(findPaths(m, n, maxlocomote, Row, Column)); |
20
Time Complexity: O(m * n * maxlocomote)
Auxiliary space: O(m * n * maxlocomote)
Contact Us