There is an island represented by a matrix. You are somewhere on the island at location (x,y)
. If you jump n
times, what is the probability you will survive? Survival means after n
jumps you must be on the island.
My solution: I applied flood fill algorithm
in which I allowed to move in all directions (i.e. N, W, E, S) and checked if before n
jumps I was off the island then increment the failure
counter, otherwise increment the success
counter.
After iterating all the possible paths, the answer is ((success)/(success + failure)). It takes exponential time.
My question from you is can we do this problem in polynomial time, by using dynamic programming or any other programming technique? If yes, can you give me the concept behind that technique?
EDIT: MY CODE
#include<iostream>
using namespace std;
double probability_of_survival(int n, int m, int x, int y, int jumps) {
int success = 0;
int failure = 0;
probability_of_survival_utility_func(n, m, x, y, 0, jumps, &sucess, &failure);
return (double)((success)/(failure+success));
}
void probability_of_survival_utility_func(int n, int m, int x, int y, int jump_made, int jumps, int *success, int *failure) {
if(x > m || x < 0 || y > n || y < 0) { (*failure)++; return;}
if(jump_made == jumps) { (*success)++; return;}
probability_of_survival_utility_func(n, m, x+1, y, jump_made++, jumps, success, failure);
probability_of_survival_utility_func(n, m, x, y+1, jump_made++, jumps, success, failure);
probability_of_survival_utility_func(n, m, x-1, y, jump_made++, jumps, success, failure);
probability_of_survival_utility_func(n, m, x, y-1, jump_made++, jumps, success, failure);
}