Home » Interview coding problems/challenges

Matrix Probability

Matrix Probability: Given a rectangular matrix of size N*M, calculate the Probability that after K moves from a given position (i, j) in the matrix.
Submitted by Divyansh Jaipuriyar, on August 21, 2020

Problem statement

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

Solution Approach

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 issafe function 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 issolve function 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 Complexity for the above approach is Exponential.

Space Complexity for the above approach is Constant.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//it return true if we are under
//valid index bound otherwise false.
bool issafe(ll x, ll y, ll n, ll m)
{
    //under valid index bound.
    if (x >= 0 and x < n and y >= 0 and y < m)
        return true;
    else //out of index bound
        return false;
}

//solve function which will find
//overall probability for K moves.
double solve(ll x, ll y, ll n, ll m, ll k)
{
    //if index range is out of bound.
    if (issafe(x, y, n, m) == false)
        return 0;

    //if all K moves have been completed.
    if (k == 0)
        return 1;

    //initialize probability variable p
    //with 0 value.
    double p = 0;

    //here .25 is multiplied with each move
    //because of equal probable movement.

    //perform down movement.
    p += solve(x + 1, y, n, m, k - 1) * .25;
    //perform up movement.
    p += solve(x - 1, y, n, m, k - 1) * .25;
    //perform right movement.
    p += solve(x, y + 1, n, m, k - 1) * .25;
    //perform left movement.
    p += solve(x, y - 1, n, m, k - 1) * .25;

    return p;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll N, M, K;
        cin >> N >> M;

        ll x, y;
        cout << "Enter initial position: ";
        cin >> x >> y;

        cout << "Enter moves: ";
        cin >> K;

        cout << "Final Probability: ";
        cout << solve(x, y, N, M, K) << "\n";
    }
 
    return 0;
}

Output

Enter number of test cases: 2
Enter size of matrix: 3 4
Enter initial position: 1 2
Enter moves: 3
Final Probability: 0.609375
Enter size of matrix: 5 5 
Enter initial position: 1 1
Enter moves: 2
Final Probability: 0.875