# Find Probability that a Person is Alive after Taking N steps on an Island

Given an island in the form of square matrix and a point inside the matrix where a person is standing. The person is allowed to move one step in any direction (right, left, top, down) on the matrix. If he steps outside the matrix, he dies. Calculate the probability that he is alive after he walks n steps on the island.

For example,

Input: 2 x 2 matrix
Starting coordinates – (0, 0)
Number of steps = 1

Output:Alive Probability is 0.5

Input: 3 x 3 matrix
Starting coordinates – (1, 1)
Number of steps = 1

Output:Alive Probability is 1

Input: 3 x 3 matrix
Starting coordinates – (0, 0)
Number of steps = 3

Output:Alive Probability is 0.25

Below solution assumes all steps carry equal probability i.e. 1/4 or 0.25. It can easily be modified to handle unequal probabilities.

We can easily solve this problem with the help of Dynamic Programming. For given position (x, y) and remaining steps n, the main problem can easily be divided into sub-problems –

Prob(x, y, n) = (Prob(x – 1, y, n – 1) + Prob(x + 1, y, n – 1) +
Prob(x, y – 1, n – 1) + Prob(x, y + 1, n – 1)) / 4.

Below is C++/Java implementation of the idea:

## C++

Output:

Alive probability is 0.25

## Java

Output:

Alive probability is 0.25

(3 votes, average: 3.67 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂