Given three integers N, M and K, where N and M are the dimensions of the matrix and K is the maximum possible steps, the task is to count the number ways to start from (0, 0) and return traversing the matrix by using K steps only.
Note: In each step, one can move up, down, left, right, or stay at the current position. The answer could be large, so print the answer modulo 109 + 7
Examples:
Input: N = 2, M = 2, K = 2
Output: 3
Explanation:
Three ways are:
1)Stay, Stay.
2)Up, Down
3)Right, Left
Input: N = 3, M = 3, K = 4
Output: 23
Approach: The problem can also be solved using Memoization technique. Follow the steps below to solve the problem:
- Starting from position (0, 0), recursively call every possible position and decrease the value of steps by 1.
- Create a 3D array of size N * M * K ( DP[N][M][S] )
Possible ways for each step
can be calculated by:
DP[i][j][k]
= Recursion(i+1, j, k-1) +
Recursion(i-1, j, k-1) +
Recursion(i, j-1, k-1) +
Recursion(i, j+1, k-1) +
Recursion(i, j, k-1).
With base condition returning 0,
whenever
i >= l or i = b or j < 0 or k < 0.
Below is the implementation of the above approach:
C++
// C++ program to count total// number of ways to return// to origin after completing// given number of steps.#include <bits/stdc++.h>using namespace std;#define MOD 1000000007long long dp[101][101][101];int N, M, K;// Function Initialize dp[][][]// array with -1void Initialize(){ for (int i = 0; i <= 100; i++) for (int j = 0; j <= 100; j++) for (int z = 0; z <= 100; z++) dp[i][j][z] = -1;}// Function returns the total countint CountWays(int i, int j, int k){ if (i >= N || i < 0 || j >= M || j < 0 || k < 0) return 0; if (i == 0 && j == 0 && k == 0) return 1; if (dp[i][j][k] != -1) return dp[i][j][k]; else dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD + CountWays(i - 1, j, k - 1) % MOD + CountWays(i, j - 1, k - 1) % MOD + CountWays(i, j + 1, k - 1) % MOD + CountWays(i, j, k - 1) % MOD) % MOD; return dp[i][j][k];}// Driver Programint main(){ N = 3; M = 3; K = 4; Initialize(); cout << CountWays(0, 0, K) << "\n"; return 0;} |
Java
// Java program to count total // number of ways to return // to origin after completing // given number of steps. class GFG{ static int [][][] dp = new int[101][101][101]; static int N, M, K;static int MOD = 1000000007; // Function Initialize dp[][][] // array with -1 public static void Initialize() { for(int i = 0; i <= 100; i++) for(int j = 0; j <= 100; j++) for(int z = 0; z <= 100; z++) dp[i][j][z] = -1; } // Function returns the total count public static int CountWays(int i, int j, int k) { if (i >= N || i < 0 || j >= M || j < 0 || k < 0) return 0; if (i == 0 && j == 0 && k == 0) return 1; if (dp[i][j][k] != -1) return dp[i][j][k]; else dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD + CountWays(i - 1, j, k - 1) % MOD + CountWays(i, j - 1, k - 1) % MOD + CountWays(i, j + 1, k - 1) % MOD + CountWays(i, j, k - 1) % MOD) % MOD; return dp[i][j][k]; } // Driver codepublic static void main(String[] args) { N = 3; M = 3; K = 4; Initialize(); System.out.println(CountWays(0, 0, K));} } // This code is contributed by grand_master |
Python3
# Python3 program to count total# number of ways to return# to origin after completing# given number of steps.MOD = 1000000007dp = [[[0 for i in range(101)] for i in range(101)] for i in range(101)]N, M, K = 0, 0, 0# Function Initialize dp[][][]# array with -1def Initialize(): for i in range(101): for j in range(101): for z in range(101): dp[i][j][z] = -1# Function returns the total countdef CountWays(i, j, k): if (i >= N or i < 0 or j >= M or j < 0 or k < 0): return 0 if (i == 0 and j == 0 and k == 0): return 1 if (dp[i][j][k] != -1): return dp[i][j][k] else: dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD + CountWays(i - 1, j, k - 1) % MOD + CountWays(i, j - 1, k - 1) % MOD + CountWays(i, j + 1, k - 1) % MOD + CountWays(i, j, k - 1) % MOD) % MOD return dp[i][j][k]# Driver codeif __name__ == '__main__': N = 3 M = 3 K = 4 Initialize() print(CountWays(0, 0, K))# This code is contributed by mohit kumar 29 |
C#
// C# program to count total // number of ways to return // to origin after completing // given number of steps. using System;class GFG{ static int [,,] dp = new int[101, 101, 101]; static int N, M, K; static int MOD = 1000000007; // Function Initialize [,]dp[] // array with -1 public static void Initialize() { for(int i = 0; i <= 100; i++) for(int j = 0; j <= 100; j++) for(int z = 0; z <= 100; z++) dp[i, j, z] = -1; } // Function returns the total count public static int CountWays(int i, int j, int k) { if (i >= N || i < 0 || j >= M || j < 0 || k < 0) return 0; if (i == 0 && j == 0 && k == 0) return 1; if (dp[i, j, k] != -1) return dp[i, j, k]; else dp[i, j, k] = (CountWays(i + 1, j, k - 1) % MOD + CountWays(i - 1, j, k - 1) % MOD + CountWays(i, j - 1, k - 1) % MOD + CountWays(i, j + 1, k - 1) % MOD + CountWays(i, j, k - 1) % MOD) % MOD; return dp[i, j, k]; } // Driver code public static void Main(String[] args) { N = 3; M = 3; K = 4; Initialize(); Console.WriteLine(CountWays(0, 0, K)); } } // This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to count total// number of ways to return// to origin after completing// given number of steps.var MOD = 1000000007;var dp = Array.from(Array(101), ()=>Array(101));for(var i =0; i<101; i++) for(var j =0; j<101; j++) dp[i][j] = new Array(101).fill(-1);var N, M, K;// Function returns the total countfunction CountWays(i, j, k){ if (i >= N || i < 0 || j >= M || j < 0 || k < 0) return 0; if (i == 0 && j == 0 && k == 0) return 1; if (dp[i][j][k] != -1) return dp[i][j][k]; else dp[i][j][k] = (CountWays(i + 1, j, k - 1) % MOD + CountWays(i - 1, j, k - 1) % MOD + CountWays(i, j - 1, k - 1) % MOD + CountWays(i, j + 1, k - 1) % MOD + CountWays(i, j, k - 1) % MOD) % MOD; return dp[i][j][k];}// Driver ProgramN = 3;M = 3;K = 4;document.write( CountWays(0, 0, K))</script> |
Output
23
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a 3D DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases dp[0][0][0] = 1.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[0][0][k].
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;#define MOD 1000000007// Function returns the total countint CountWays(int n, int m, int k){ // Initialize dp to store // computations of subproblems int dp[k+1][n+1][m+1]; memset(dp, 0, sizeof(dp)); // Base Case dp[0][0][0] = 1; // iterate over subproblems and get the current // solution for previous computations for (int l = 1; l <= k; l++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // update DP current value dp[i][j][l] = ((i > 0 ? dp[i - 1][j][l - 1] : 0) + (i < n - 1 ? dp[i + 1][j][l - 1] : 0) + (j > 0 ? dp[i][j - 1][l - 1] : 0) + (j < m - 1 ? dp[i][j + 1][l - 1] : 0) + dp[i][j][l - 1]) % MOD; } } } // return final answer return dp[0][0][k];}// Driver Programint main(){ int N = 3; int M = 3; int K = 4; // function call cout << CountWays(N, M, K) << "\n"; return 0;}// This code is contributed by bhardwajji. |
Python3
# Python 3 program for above approachMOD = 1000000007# Function returns the total countdef CountWays(n, m, k): # Initialize dp to store # computations of subproblems dp = [[[0 for i in range(m+1)] for j in range(n+1)] for k in range(k+1)] # Base Case dp[0][0][0] = 1 # iterate over subproblems and get the current # solution for previous computations for l in range(1, k+1): for i in range(n): for j in range(m): # update DP current value dp[l][i][j] = ((dp[l-1][i-1][j] if i > 0 else 0) + (dp[l-1][i+1][j] if i < n-1 else 0) + (dp[l-1][i][j-1] if j > 0 else 0) + (dp[l-1][i][j+1] if j < m-1 else 0) + dp[l-1][i][j]) % MOD # return final answer return dp[k][0][0]# Driver Programif __name__ == "__main__": N = 3 M = 3 K = 4 # function call print(CountWays(N, M, K)) |
C#
using System;class GFG { const int MOD = 1000000007; // Function returns the total count static int CountWays(int n, int m, int k) { // Initialize dp to store // computations of subproblems int[][][] dp = new int[k + 1][][]; for (int i = 0; i <= k; i++) { dp[i] = new int[n + 1][]; for (int j = 0; j <= n; j++) { dp[i][j] = new int[m + 1]; } } // Base Case dp[0][0][0] = 1; // iterate over subproblems and get the current // solution for previous computations for (int l = 1; l <= k; l++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // update DP current value dp[l][i][j] = ((i > 0 ? dp[l - 1][i - 1][j] : 0) + (i < n - 1 ? dp[l - 1][i + 1][j] : 0) + (j > 0 ? dp[l - 1][i][j - 1] : 0) + (j < m - 1 ? dp[l - 1][i][j + 1] : 0) + dp[l - 1][i][j]) % MOD; } } } // return final answer return dp[k][0][0]; } // Driver Program static void Main(string[] args) { int N = 3; int M = 3; int K = 4; // function call Console.WriteLine(CountWays(N, M, K)); }} |
Javascript
const MOD = 1000000007;function CountWays(n, m, k) { const dp = new Array(k + 1) .fill(null) .map(() => new Array(n + 1) .fill(null) .map(() => new Array(m + 1).fill(0) ) ); // Base Case dp[0][0][0] = 1; // Iterate over subproblems and get the current solution for previous computations for (let l = 1; l <= k; l++) { for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // Update DP current value dp[l][i][j] = ( (i > 0 ? dp[l - 1][i - 1][j] : 0) + (i < n - 1 ? dp[l - 1][i + 1][j] : 0) + (j > 0 ? dp[l - 1][i][j - 1] : 0) + (j < m - 1 ? dp[l - 1][i][j + 1] : 0) + dp[l - 1][i][j] ) % MOD; } } } // Return final answer return dp[k][0][0];}// Driver Programconst N = 3;const M = 3;const K = 4;// Function callconsole.log(CountWays(N, M, K)); |
Output
23
Time Complexity : O(N*K*M)
Auxiliary Space : O(N*K*M)
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!
