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

## 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

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

```2
3 3
4 4

6 20```

## 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

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

• 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=’ ‘)

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

• Vilo

This might show TLE error

• 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