# Matrix Probability

Given a rectangular matrix of size *N*M*, we can move from the current cell in 4 directions with equal probability. The 4 directions are right, left, top, or bottom. Calculate the Probability that after *K* moves from a given position *(i, j)* in the matrix, we will not cross the boundaries of the matrix at any point.

**Input:**

The first line of input consists of *T* number of test cases, each test case consists of two integer *N* and *M* the size of the matrix and next line consist of two integers *(i, j)* the starting position and the last line consist of *K*, the number of moves that you have to make.

**Output:**

Print the probability that after *K* moves from given position *(i,j)* we will not cross boundaries of the matrix at any point.

**Examples:**

Input:
T=1
N=3,M=4
1 2
K=3
Output:
0.609375
Input:
T=1
N=5,M=5
1 1
K=2
Output:
0.875

Since we can move each of the four sides from the current position (i,j) with equal probability, which means we have 1/4 chances for each move, we will calculate the overall probability with the help of the Depth-first search approach based on recursion.

We will simply return 0 if the position is out of index bound and we return 1 is we have completed all moves K.

We will use two functions as

issafefunction which will return true or false depending upon the position, if we are under the index bound of the matrix then it returns true otherwise false.Another function

issolvefunction which will return the probability, the base condition of the recursive call is if we are not in a safe location then it would simply return 0 and if we have exhausted all our moves then it would return 1. Other possible causes are the movement in all four directions for that we used a variable p.Time Complexityfor the above approach isExponential.Space Complexityfor the above approach isConstant.C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: