Python Program for Maneuvering a cave (TCS Codevita) | PrepInsta

Python Program for Maneuvering a cave

Maneuvering a Cave Problem

Maneuvering a Cave Problem is a 2-D array manipulation problem, which was asked in this year TCS CodeVita 2020 Season 9 coding competition, as a sample question. It is a pretty tough problem, but one can solve it if he has good command on data structures and dynamic programming. Here we have provided a Python Solution for this problem.

 

Problem Description

The task is to count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down.

Input: 

  • First line consists of T test cases. First line of every test case consists of N and M, denoting the number of rows and number of columns respectively.

Output: 

  • Single line output i.e count of all the possible paths from top left to bottom right of a m x n matrix..

Constraints:

  • 1<=T<=100
  • 1<=N<=100
  • 1<=M<=100

 

Python Code

def calculate(a, b):
    if a == 1 or b == 1:
        return 1
    else:
        return calculate(a - 1, b) + calculate(a, b - 1)
result = []    
test = int(input())

for i in range(test):
    a, b = map(int,input().split())
    result.append(calculate(a, b))
    
for i in result:
    print(i,end=" ")
Output:
2
3 3 
4 4 
6 20

Maneuvering a cave Problem in Other Coding Languages

C

 To find the solution of Maneuvering a Cave problem in C Programming language click on the button below:

C

C++

To find the solution of Maneuvering a Cave problem in C++  Programming language click on the button below:

C++

Java

To find the solution of Maneuvering a cave problem in Java Programming language click on the button below:

Java

6 comments on “Python Program for Maneuvering a cave (TCS Codevita) | PrepInsta”


  • Sukesh

    #Here I’m coded only for Square matrix
    Test_case = int(input())
    matrix_list = [list(map(int, input().split())) for _ in range(Test_case)]
    Ans = []
    for i in range(Test_case):
    node = ((matrix_list[i][0]) – 1) + ((matrix_list[i][1]) – 1)
    reduce = (node + (node – 1)) * matrix_list[i][0]
    Ans.append(abs((2 ** node) – reduce))
    for j in range(Test_case):
    print(Ans[j], end=’ ‘)


  • Mohammad

    This code will run for Larger test cases :

    Dynamic programming Bottom-up approach :

    a = int(input())
    b = int(input())

    def op(a,b):
    dp = [[0 for i in range(b+1)] for j in range(a+1)]
    for i in range(a+1):
    for j in range(b+1):
    if i==1 or j==1:
    dp[i][j] = 1
    else:
    dp[i][j] = dp[i-1][j]+dp[i][j-1]
    return dp[a][b]
    print(op(a,b))


    • Care

      No Vilo, it won’t. Try executing the code on an online compiler, as sometimes the IDE may have been customized and show errors