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

February 5, 2022

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.

 

Python Program for Maneuvering a cave
All TCS CodeVita Questions with Answers

Problem Description

Cave Explorer Program in Python

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=" ")

Input/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

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


  • Abhishek

    Using Mathematics:
    Done by calculating paths possible for each block, starting from column(m-2), because the path in column(m) is 1 and paths in column(m-1) are m-1
    from sys import stdin, stdout

    for _ in range(int(stdin.readline())):
    n , m = map(int , stdin.readline().split())
    if n == 1 or m == 1: stdout.write(‘1\n’)
    else:
    colSum = [1]*(m-1)
    top = []
    prevSum = m-1
    totSum = 0
    for i in range(n-2):
    top.append(colSum[0])
    for j in range(m-2):
    totSum += prevSum
    tempSum = colSum[j]
    colSum[j] = prevSum
    prevSum -= tempSum
    # print(colSum, totSum)
    prevSum = totSum + 1
    totSum = 0
    top.append(colSum[0])
    totalPaths = sum(colSum) + sum(top)
    stdout.write(str(totalPaths)+”\n”)


  • Shaswata

    #using DP

    def remain_box(n,m,memo={}):
    print(memo)
    temp = str(n)+str(m)
    if n<=1 or m<=1:
    memo[temp] = 1
    return 1
    elif temp in memo:
    return memo[temp]
    con = remain_box(n-1, m,memo) + remain_box(n, m-1,memo)
    memo[temp] = con
    return con

    result=[]
    for i in range(int(input())):
    row = int(input())
    column = int(input())
    result.append(remain_box(row, column))
    print(' '.join(map(str,result)))


  • 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