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.
Read full article from 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;
}