# Island Probability

You are standing in some location *(x, y)* on an island, given in form of a matrix of size *N*M*, you are allowed to move in all four directions left, right, up and down. You can move only one step at a time, if you step out of the matrix region then you die. Calculate the probability of being alive after moving *n* steps.

**Problem description:**

The problem wants you to use knowledge of probability, you are standing at some location in the matrix and you are allowed to move in all four directions from the current location as left, right, down and up, but you need to keep in mind that you can only take *K* steps and if you fall out you die that is probability becomes 0 and if you utilized all *K* moves and you are under index range then the probability is 1. So you need to develop some logic that you can maximize the probability of surviving in that island.

**Input:**

The first line of the input is the *T* number of test cases, each test case consists of *N*, size of the given *matrix(N*N)*, and the starting point *(x,y)* in the following line and the number of moves *k* that he has.

**Output:**

You are required to print the probability of person being alive after *n* moves.

**Examples:**

Input:
T=1
N=3
x=1,y=1
k=4
Output:
0.375
Input:
T=1
N=4
x=2,y=2
k=3
Output:
0.71875

Recursion Approach:We will use a recursive function to solve this problem, we will create a solve function which will take a number of steps that we have, the coordinates as its input and return the probability of being alive if the number of steps remaining is 0 and we are under that matrix boundary then we simply 1 otherwise we will recursively call solve function in all four directions until we are left with 0 moves remaining.

The probability of traveling in all four directions is (0.25) as all have equal probability.

let f(x, y, n) be some function then it can be defined as:

let

be some function then it can be defined as:f(x, y, n)f(x,y,n)=f(x+1,y,n-1)*.25+f(x-1,y,n-1)*.25+f(x,y-1,n-1)*.25+f(x,y+1,n-1)*.25Time complexityfor above approach in worst case is exponential.Space complexityfor above approach in worst case is constant.Dynamic Programming Approach:In this approach we will use memoization technique to optimize our solution from exponential time to some efficient time, we will create a map for storing values for different states, each time we make a recursive call we will first check it in dp table, if already calculated then simply return it otherwise we calculate it again.

Time complexityfor the above approach in the worst case is:O(n*n*n)Space complexityfor the above approach in the worst case is:O(n*n*n)1) C++ Implementation (Recursion)Output:2) C++ Implementation (Dynamic Programming):

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: