## Wednesday, June 1, 2016

### 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;`
`}`