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

Comments and Discussions!