A matrix probability question - GeeksforGeeks

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

The idea is to perform something similar to DFS. We recursively traverse in each of the 4 allowed direction and for each cell encountered, we calculate the required probability with one less move. As each direction has equal probability, each direction will contribute to 1/4 of total probability of that cell i.e. 0.25. We return 0 if we step outside the matrix and return 1 if N steps are completed without crossing matrix boundaries.

// check if (x, y) is valid matrix coordinate

bool isSafe(int x, int y, int m, int n)

{

    return (x >= 0 && x < m && y >= 0 && y < n);

}

 

// Function to calculate probability that after N

// moves from a given position (x, y) in m x n matrix,

// boundaries of the matrix will not be crossed.

double findProbability(int m, int n, int x, int y, int N)

{

    // boundary crossed

    if (!isSafe(x, y, m, n))

        return 0.0;

 

    // N steps taken

    if (N == 0)

        return 1.0;

 

    // Initialize result

    double prob = 0.0;

 

    // move up

    prob += findProbability(m, n, x - 1, y, N - 1) * 0.25;

 

    // move right

    prob += findProbability(m, n, x, y + 1, N - 1) * 0.25;

 

    // move down

    prob += findProbability(m, n, x + 1, y, N - 1) * 0.25;

 

    // move left

    prob += findProbability(m, n, x, y - 1, N - 1) * 0.25;

 

    return prob;

}

Read full article from A matrix probability question - GeeksforGeeks