PROBLEM LINK:
Author: Learner Club
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
In short problem was to calculate the probability of taking n steps in either of the four direction with the restriction that same position must not be traversed again and the probability of taking one step in either of the four direction (N,S,E,W) is already given.
EXPLANATION:
Method O(n):
This question could be thought of in a simple brute force manner. You need to explore all possible cases of taking n steps with the restriction that the same position must not be traversed more than one time. One can use DFS to trace all possible paths and by using a mark array to ensure that one position is not visited more than once. Probability calculation is illustrated through an example -
Lets take an example
with K=2
and P(E),P(S),P(W),P(N) = 0.25 0.25 0.25 0.25
He can take his first step in any of the four direction. But in next step he is left with only three choices. Suppose he moves 1 step East direction then he can not take another step in the west direction. As it brings him to the already visited position. Therefore there are only 12 possible ways as listed below -
EN, ES, EE
WN, WS, WW
NE, NW, NN
SE, SW, SS
So the total probability will be the summation of probabilities of 12 possible ways
= (P(E)*P(N) + P(E)*P(S) + P(E)*P(E) + …)
= 0.750000
So we can simply apply Depth First Search and keep counting the probability at each step until we exhaust all the K steps.