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.
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.
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.
You are required to print the probability of person being alive after n moves.