CareerCup

I presume that the probabilities of move up/donw/left/right are equal(0.25).
Then P(x, y, n, step) = (P(x-1, y, n, step-1) + P(x+1, y, n, step-1) + P(x, y-1, n, step-1) + P(x, y+1, n, step-1)) / 4.
(x, y) is the position. (n) is the size of island. (step) is the remaining step.
The following code is my Java implementation with some simple tests.
Dynamic Programming is also used.

import java.util.*;

class ProbabilityOfAlive
{
  public static double probabilityOfAlive(int x, int y, int n)
  {
    if (x < 0 || x > (n - 1) || y < 0 || y > (n - 1) || n < 1) {return 0.0;}
    return probabilityOfAlive(x, y, n, n, new HashMap<String, Double>());
  }

  private static double probabilityOfAlive(int x, int y, int n, int step, HashMap<String, Double> map)
  {
    if (0 == step) {return 1.0;}
    // if the state is already calculated, return from HashMap
    String key = "";
    {
      StringBuffer sb = new StringBuffer();
      sb.append(x + ",");
      sb.append(y + ",");
      sb.append(step + ".");
      key = sb.toString();
    }
    if (map.containsKey(key)) {return map.get(key);}
    // calculate the probability of a state
    double probability = 0.0;
    if (x > 0) {probability += 0.25 * probabilityOfAlive(x - 1, y, n, step - 1, map);}
    if (x < (n - 1)) {probability += 0.25 * probabilityOfAlive(x + 1, y, n, step - 1, map);}
    if (y > 0) {probability += 0.25 * probabilityOfAlive(x, y - 1, n, step - 1, map);}
    if (y < (n - 1)) {probability += 0.25 * probabilityOfAlive(x, y + 1, n, step - 1, map);}
    // save the result to HashMap and return
    map.put(key, probability); return probability;
  }

  public static void main(String[] args)
  {
    System.out.println("probability1 = " + probabilityOfAlive(0, 0, 1));
    System.out.println("probability2 = " + probabilityOfAlive(0, 0, 2));
    System.out.println("probability3 = " + probabilityOfAlive(0, 0, 3));
  }
}

1. Generate NxN probability matrix P(x,y,1) for all (x, y) coordinates (x & y ranges from 0 to N-1). P(x,y,1) is the probability of staying alive after taking 1 step
2. Now using this, we need to calculate the NxN probability matrix P(x,y,2) for all x and y - will be P(x,y,1) * { {Valid among P(x+1, y, 1) + P(x, y+1, 1) + P(x-1, y, 1) + P(x, y-1, 1) } / num of valid adjascent slots }. Now we have P(x,y,2) probability matrix.
3. Using induction, we can calculate P(x, y, k) using P(x, y, k-1). Repeat this N times, we have our probability matrix after N steps

float probabilityofalive(int x, int y, int N, int num_steps)
{
    if (N <= 0) return 0;
    if (x < 0 || x >= N) return 0;
    if (y < 0 || y >= N) return 0;

    if (N == 1) return 0; // only one square. first step will cause exit from island and die.

    /* Probability matrix for staying alive after K steps for all (x,y) coordinates. */
    double *P_old = calloc(N*N, sizeof(double));

    /* Probability matrix for staying alive after K+1 steps for all (x,y) coordinates. */
    double *P_new = calloc(N*N, sizeof(double));

    int i, j;
    /* Initialize for K = 1 */
    for (i = 0; i<N; i++) {
        for (j=0; j<N; j++) {
            double prob;
            if (i>0 && i<N-1 && j>0 && j<N-1) {
                prob = 1.0;
            } else if ((i == 0 || i == N-1) && (j == 0 || j == N-1)) {
                prob = 0.5;
            } else
                prob = 0.75;

            P_new[N*i + j] = prob;
        }
    }

    int k = 0;
    for (k=2; k<=num_steps; k++) { /* First step already taken in K == 1 matrix above */
        /* Copy new to old */
        for (i = 0; i<N; i++) {
            for (j=0; j<N; j++) {
                P_old[N*i+j] = P_new[N*i+j];
            }
        }

        /* Calculate new probability matrix */
        for (i=0; i<N; i++) {
            for (j=0; j<N; j++) {
                double sum_prob = 0;
                int num_prob = 0;
                if (i > 0) {
                    sum_prob += P_old[N*(i-1) + j];
                    num_prob++;
                }
                if (i < N-1) {
                    sum_prob += P_old[N*(i+1) + j];
                    num_prob++;
                }
                if (j > 0) {
                    sum_prob += P_old[N*i + (j-1)];
                    num_prob++;
                }
                if (j < N-1) {
                    sum_prob += P_old[N*i + (j+1)];
                    num_prob++;
                }

                /* New probability when person starting at (i,j) coordinate after k steps*/
                P_new[N*i + j] = P_old[N*i + j] * sum_prob/num_prob;
            }
        }
    }

    return P_new[N*x + y];
}

int main()
{
     int x = 3;
     int y = 3;
     int N = 4;
     int num_steps = N;
     float prob =  probabilityofalive(x, y, N, num_steps);

     printf("Probability of staying alive after %d steps starting at coordinates (%d, %d)  on an %d x %d grid is '%f'\n", num_steps, x, y, N, N, prob);
}

/*
     For N = 4, probability fo survival after 1 step is given below

            -------------------------------------
            |        |        |        |        |
            |  0.50  |  0.75  |  0.75  |  0.50  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.75  |  1.00  |  1.00  |  0.75  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.75  |  1.00  |  1.00  |  0.75  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.50  |  0.75  |  0.75  |  0.50  |
            |        |        |        |        |
            -------------------------------------


     Probability fo survival after 2 steps will be

            -------------------------------------
            |        |        |        |        |
            |  0.38  |  0.56  |  0.56  |  0.38  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.56  |  0.88  |  0.88  |  0.56  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.56  |  0.88  |  0.88  |  0.56  |
            |        |        |        |        |
            -------------------------------------
            |        |        |        |        |
            |  0.38  |  0.56  |  0.56  |  0.38  |
            |        |        |        |        |
            -------------------------------------

       ... and so on
  */

Believe this logic/code is correct. Please update if you find any issue

public float prob(int x, int y, int n) {
	if ((x<0)||(y<0)||(x>=n)||(y>=n))
		return 0;
	else if (n==1)
		return 1;
	return (prob(x-1, y, n-1)+prob(x, y-1, n-1)+
		prob(x+1, y, n-1)+prob(x, y+1, n-1))/4;
}

Efficient Solution in Python (with tests)

This is a DP solution that only computes one octant of the matrix, since all the other octants are just reflections. It also defers dividing by powers of four until the end.

def test():
    assert 1.0 == probability_of_alive(5, 0, 0, 0)
    assert 0.5 == probability_of_alive(5, 1, 0, 0)
    assert 0.75 == probability_of_alive(5, 1, 1, 4)
    assert 1.0 == probability_of_alive(5, 2, 2, 2)
    assert 0.9375 == probability_of_alive(5, 3, 2, 2)

def probability_of_alive(N, n, x, y):
    dct = get_survival_dct(N, n)
    return 1.0 * lookup(dct, N, x, y) / (4**n)

def get_survival_dct(N, n):
    # This returns a dictionary where keys
    # are (x,y) tuples and it only has values
    # for the WNW octant of the island, since
    # other values can be calculated via
    # horizontal, vertical, and diagonal
    # reflection.  Values are probabilities
    # of survival * (4**n).
    dct = {}
    for i in range((N+1)/2):
        for j in range(i, (N+1)/2):
            dct[(i,j)] = 1
    for step in range(n):
        new_dct = {}
        for i in range((N+1)/2):
            for j in range(i, (N+1)/2):
                new_dct[(i,j)] = \
                    lookup(dct, N, i+1, j) + \
                    lookup(dct, N, i, j+1) + \
                    lookup(dct, N, i-1, j) + \
                    lookup(dct, N, i, j-1)
        dct = new_dct
    return dct

def lookup(dct, N, i, j):
    if N - i - 1< i: i = N - i - 1
    if N - j - 1< j: j = N - j - 1
    if j < i: i, j = j, i
    return dct.get((i,j), 0)

def print_probability_matrix(N, dct):
    for i in range(N):
        print [lookup(dct, N, i, j) for j in range(N)]

N = 5
for n in range(4):
    dct = get_survival_dct(N, n)
    print_probability_matrix(N, dct)
    print
test()

The program's output shows that sample matrices for N=5.

[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]

[2, 3, 3, 3, 2]
[3, 4, 4, 4, 3]
[3, 4, 4, 4, 3]
[3, 4, 4, 4, 3]
[2, 3, 3, 3, 2]

[6, 9, 10, 9, 6]
[9, 14, 15, 14, 9]
[10, 15, 16, 15, 10]
[9, 14, 15, 14, 9]
[6, 9, 10, 9, 6]

[18, 30, 33, 30, 18]
[30, 48, 54, 48, 30]
[33, 54, 60, 54, 33]
[30, 48, 54, 48, 30]
[18, 30, 33, 30, 18]

#include <iostream>
#include <assert.h>
using namespace std;

#define N 5

float probabilityofalive(int x,int y, int n){
	assert( x>=0 && x<N && y>=0 && y<N);
	
	if (n==1) {
		if (x==0 && y==0 || x==0 && y==N-1 || x==N-1 && y==0 || x==N-1 && y==N-1) {
			return 0.5;
		} else if (x==0 || x==N-1 || y==0 || y==N-1) {
			return 0.25;
		} else {
			return 1;
		}
	}
	
	float p_left, p_right, p_up, p_down;
	
	if (0 <= x-1) {
		p_left = probabilityofalive(x-1, y, n-1);
	} else {
		p_left = 0;
	}
	
	if (x+1<N) {
		p_right = probabilityofalive(x+1, y, n-1);
	} else {
		p_right = 0;
	}
	
	if (0<=y-1) {
		p_up = probabilityofalive(x, y-1, n-1);
	} else {
		p_up = 0;
	}

	if (y+1<N) {
		p_down = probabilityofalive(x, y+1, n-1);
	} else {
		p_down = 0;
	}

	
	return 0.25*( p_left+p_right+p_up+p_down );

}

int main ()
{

	cout << probabilityofalive(2, 2, 5) << endl;
	
	return 0;
}

double solve(int x, int y, int k)
   {
            if (x < 0 || x > n || y < 0 || y > n) return 0;
            if (k == 0) return 1.0;
            double ret(0.0);
            if (x+1 < n) ret += solve(x+1, y, k-1);
            if (x-1 >=0) ret += solve(x-1, y, k-1);
            if (y-1 >=0 ) ret += solve(x, y-1, k-1);
            if (y+1 < n) ret += solve(x, y+1, k-1);
            return 0.25 * ret; 
   }

My solution in C++. We fill a matrix of size n*N*N in O(n*N^2) time :

float probabilityofalive(int x, int y, int n) {
    float P[n + 1][N][N];
    int i, j, k;
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            P[0][i][j] = 1.;
        }
    }
    for (k = 1; k <= n; ++k) {
        for (i = 0; i < N; ++i) {
            for (j = 0; j < N; ++j) {
                P[k][i][j] = 0.;
                if (i < N - 1)
                    P[k][i][j] += P[k - 1][i + 1][j];
                if (i > 0)
                    P[k][i][j] += P[k - 1][i - 1][j];
                if (j < N - 1)
                    P[k][i][j] += P[k - 1][i][j + 1];
                if (j > 0)
                    P[k][i][j] += P[k - 1][i][j - 1];
                P[k][i][j] *= 0.25;
            }
        }
    }
    return P[n][x][y];
}

Psuedocode for probabilityofdead :

float probabilityofdead(int x, int y, int n)
{
	
	if(x>0 && y>0 )
       {	

        	if (N-1-x >= n &&  N-1-y>=n  && x>=n && y>=n && n>=0)
	return 1;
     
      	if( x==N-1 && y>0 && y< N-1 & n>=1)
	return 0.25;
    
 	if( y==N-1 && x>0 && x< N-1 & n>=1)
	return 0.25;
	
	if( x==0 && y>0 && y< N-1 & n>=1)
	return 0.25;

	if( y==0 && x>0 && x< N-1 & n>=1)
	return 0.25;

	if(x==0 && y==0 || x==N-1 && y==0 || y==N-1 && x==0 || x==N-1 && y==N-1)
	return 0.75;

	n--;

	return 	probabilityofdead(x+1,y,n)  + 
			probabilityofdead(x,y+1,n)  +
    			probabilityofdead(x-1,y,n)   +
			probabilityofdead(x,y-1,n) ;

     }
else

return 0;
}

Hence ,probabilityofalive= 1- probabilityofdead

A DP problem. Let's say the person is at (x0, y0) initially(instead of (x, y) in the question)
Build a table W(n, N, N) whose entry W(k, x, y) is the number of ways to get to (x, y) from initial location(x0, y0) after k steps.
Now, without considering the border,

W(k + 1, x, y) = W(k, x - 1, y) + W(k, x, y - 1) + W(k, x + 1, y) + W(k, x, y + 1)

Then build W up to n steps, again, without considering the border.
After that, just count the percentage of the locations (a, b) in W(n, a, b) that are out of the border, this is the probability.

This can be solved using DP

int fall =0;
int calProb(int n, int m, int **arr)
{
     if(n ==0 && m == 0)
	 return 1;
     else if( m<0 || n< 0)
     {
         fall++;
         return 0;
     }
    else
    {
          return CallProb(n-1,m,**arr) + CallProb(n,m-1,**arr) + CallProb(n-1,m-1,**arr);
    }
}

def probDeadHelper(x,y,n,N,deadAlive):
    if n==0:
        deadAlive[1] = deadAlive[1]+1
        return
    if (x<0 or x >=N or y <0 or y >=N):
        deadAlive[0] = deadAlive[0] +1
        return
    probDeadHelper(x-1,y,n-1,N,deadAlive)
    probDeadHelper(x+1,y,n-1,N,deadAlive)
    probDeadHelper(x,y-1,n-1,N,deadAlive)
    probDeadHelper(x,y+1,n-1,N,deadAlive)
def probDead(x,y,n,N):
    deadAlive = [0,0]
    probDeadHelper(x,y,n,N,deadAlive)
    dead = deadAlive[0]
    alive = deadAlive[1]
    return (alive/(alive+dead))

Pseudo code

- Add x, y, N-x, N-y into sorted array
- assume highest to lowest order is N-x, y, N-y, x for now
- if n > N-x return 1 (means if person moves n steps at all any direction he will be dead)
- if n < x return 0 ( means if person moves n steps any dir he will be alive)
- if n is between N-x and y return .75
And so on

My Idea :
1> For area outside the NXM, the death Prob is 1, what ever the step is. (step>=0)
2> For area inside the NxM and step=0, death Prob is zero.
3> For Other x, y, and step, probDeath(x,y,step)=1/4*(probDeath(x-1,y, step-1) + probDeath(x+1,y, step-1)+probDeath(x,y-1, step-1) +probDeath(x,y+1, step01)). Assume the person runs randomly.
4> The logic above also added a array to store the shared calculated result (as does dynamic programming) to save the computation time during the recursive call.
5> ProbLive(x,y, step)=1-ProbDeath(x,y,step).

My Code:

typedef struct{
        double  *pProb;
        int     w;
        int     h;
        int     step;
} squareProb_t;

void   squareProbInit(squareProb_t *pCb, int w, int h, int maxStep)
{
        int     count;
        if(NULL==pCb||1>w||1>h)
                return;
        pCb->w=w;
        pCb->h=h;
        pCb->step=maxStep;
        pCb->pProb=malloc(sizeof(double)*w*h*(maxStep));
        if(NULL==pCb->pProb)
                return;
        for(count=0;count<w*h*(maxStep);count++)
                pCb->pProb[count]=-1.0;
        return;
}
double squareProbDead(squareProb_t *pCb, int x, int y, int step)
{
        int     count;
        if(NULL==pCb)
                return 0;
        if(0>step||pCb->step<step)
                return 0;
        if(x<0||x>=pCb->w||y<0||y>=pCb->h)
        {
                printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step, 1.0);
                return 1;
        }
        if(step==0)
        {
                printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step, 0.0);
                return 0;
        }
        count=(y*pCb->w+x)*pCb->step+step-1;

        if(-1.0==pCb->pProb[count])
        {
                step--;
                pCb->pProb[count]=(squareProbDead(pCb, x-1,y, step)+
                                   squareProbDead(pCb, x+1,y, step)+
                                   squareProbDead(pCb, x,y-1, step)+
                                   squareProbDead(pCb, x,y+1, step))/4;
                printf("  ==>");
        }
        printf("(x=%d, y=%d, step=%d) ==> %f\n", x, y, step+1, pCb->pProb[count]);
        return pCb->pProb[count];
}

def deadprobability(n, N, x0, y0):
    waystodie = 0
    W = [[[0 for y in range(0, N)] for x in range(0, N)] for k in range(0, n + 1)]
    W[0][x0][y0] = 1

    for k in range(1, n + 1):
        for x in range(0, N):
            for y in range(0, N):
                if x == 0:
                    waystodie +=  W[k - 1][x][y]
                if x == N - 1:
                    waystodie += W[k - 1][x][y]
                if y == 0:
                    waystodie += W[k - 1][x][y]
                if y == N - 1:
                    waystodie += W[k - 1][x][y]
                if x > 0:
                    W[k][x][y] += W[k - 1][x - 1][y]
                if x < N - 1:
                    W[k][x][y] += W[k - 1][x + 1][y]
                if y > 0:
                    W[k][x][y] += W[k - 1][x][y - 1]
                if y < N - 1:
                    W[k][x][y] += W[k - 1][x][y + 1]
        print str(W)

    waysalive = 0
    for x in range(0, N):
        for y in range(0, N):
            waysalive += W[n][x][y]

    probalive = 1.0 - waystodie / ((waystodie + waysalive) * 1.0)
    print waystodie, waysalive, probalive

def test(n, N, x0, y0):
    print 'Initial at (%d, %d) in %dx%d island, after %d steps'%(x0, y0, N, N, n)
    deadprobability(n, N, x0, y0)

test(1, 1, 0, 0)
test(2, 1, 0, 0)
test(2, 2, 0, 0)
test(2, 3, 1, 1)

#include <iostream>
#include <vector>

bool isDead(unsigned int N, int x, int y)
{
    if (x < 0 || x >= N || y < 0 || y >= N)
    {
        return true;
    }
    return false;
}

static unsigned int deadCount = 0;
static unsigned int overallCount = 0;

void computeAllPaths(int x, int y, int n, int N)
{
    if (isDead(N, x, y))
    {
        deadCount += 1;
        overallCount += 1;
    }
    else
    {
        if ( n > 0)
        {
            computeAllPaths(x-1, y, n-1, N);
            computeAllPaths(x + 1, y, n-1, N);
            computeAllPaths(x, y - 1, n-1, N);
            computeAllPaths(x, y + 1, n-1, N);
        }
        else
        {
            overallCount += 1;
        }
    }
}

float probabilityofalive(int x, int y, int n, int N)
{
    if (x >= 0 && x < N && y >=0 && y< N)
    {
        deadCount = 0;
        overallCount = 0;

        computeAllPaths(x, y, n, N);

        return (float) deadCount / (float) overallCount;

    }

    return 1.0;
}

void main()
{
    int x = 4;
    int y = 4;
    int n = 5;
    int N = 6;
    printf("probability (x:%d, y:%d, N:%d, n:%d) = %f", x, y, N, n, probabilityofalive(x,y,n,N));

    getchar();
}

public static double prop2Alive(int x,int y, int N,int step){
if(x<0 ||y<0||x>=N||y>=N) return 0;
else {
if(step==0) return 1;

return (prop2Alive(x-1,y,N,step-1)+prop2Alive(x,y-1,N,step-1)+prop2Alive(x+1,y,N,step-1)+prop2Alive(x,y+1,N,step-1))/4;
}
}

This is my code, it could be optimized by only calling checkBoundary on the borders and exiting the main loop once you reach i==x && j==y && steps == n, but i was going for simplicity of the code here.

public class ProbabilityOfAlive {
	public static double probabilityOfAlive(int x, int y, int n){
		int[][][] island = new int[n][n][2];
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				island[i][j][1] = checkBoundary(i,j, n);
		for(int steps=2;steps <= n; steps++)
			for(int i=0; i<n; i++)
				for(int j=0; j<n; j++){
					int up = (i == 0) ? (int)Math.pow(4, steps-1) : island[i-1][j][(steps-1)%2];
					int down = (i == n-1) ? (int)Math.pow(4, steps-1) : island[i+1][j][(steps-1)%2];
					int left = (j == 0) ? (int)Math.pow(4, steps-1) : island[i][j-1][(steps-1)%2];
					int right = (j == n-1 ) ? (int)Math.pow(4, steps-1) : island[i][j+1][(steps-1)%2];
					island[i][j][steps%2] = up + down+left+right;
				}
		return 1-island[x][y][n%2]/Math.pow(4, n);
	}
	private static int checkBoundary(int x, int y, int n){
		n--;
		if(x % n == 0 && y % n == 0)
			return 2;
		if(x % n == 0 || y % n == 0)
			return 1;
		return 0;
	}
}

For below method,
k: number steps.
N: size of square matrix island.

Considering array alive[N][N][2], where each element in alive[i][j][steps%2] will keep count of the favourable cases.
To calculate this count we just need the result from previous steps, i.e.,
top = alive[i-1][j][(steps-1)%2];
down = alive[i+1][j][(steps-1)%2];
left = alive[i][j-1][(steps-1)%2];
right = alive[i][j+1][(steps-1)%2];

So, favourable cases for alive[i][j][steps%2] = up + down + left + right;

// DYNAMIC PROGRAMMING WITH TABULATION IN C++ LANGAUGE.
// S = O(N^2); T = O(K*N*N)
double getProbabilityOfAlive(int x, int y, int k, int N){
    int[][][] alive = new int[N][N][2];

    // FOR STEPS=0, THIS IS JUST FOR UNDERSTANDING PURPOSE AND CAN BE REMOVED FROM METHOD.
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            alive[i][j][0] = 0; // steps==0.

    // FOR STEPS=1, NON-CORNER ELEMENTS AND EDGE ELEMENTS OF MATRIX.
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            if( (i>=1) && (i<=(N-2)) && (j>=1) && (j<=(N-2)) ) {
                alive[i][j][1] = 4; // steps==4.
            } else if( (i==0) || (i==(N-1)) || (j==0) || (j==(N-1)) ) {
                alive[i][j][1] = 3; // steps==3.
            }
        }
    }
    alive [0][0][1]     = 2; // for corners of matrix.
    alive [0][N-1][1]   = 2; // for corners of matrix.
    alive [N-1][0][1]   = 2; // for corners of matrix.
    alive [N-1][N-1][1] = 2; // for corners of matrix.


    // COUNT ALL FAVOURABLE CASES.
    for(steps=2;steps <= k; steps++)
        for(i=0; i<N; i++)
            for(j=0; j<N; j++){
                up    = (i == 0)    ? 0 : alive[i-1][j][(steps-1)%2];
                down  = (i == N-1)  ? 0 : alive[i+1][j][(steps-1)%2];
                left  = (j == 0)    ? 0 : alive[i][j-1][(steps-1)%2];
                right = (j == N-1 ) ? 0 : alive[i][j+1][(steps-1)%2];

                alive[i][j][steps%2] = up + down + left + right;
            }

    totalCases = pow(4, n);
    return (alive / totalCases);
}

Model it as a graph search see how many nodes you visited and how many times you result in a death
{{


def probabilityalive(x,y,nmoves,N):
deaths,moves = getprob((x,y),nmoves,N,0,set())
return 1 - deaths/(1.0 * (moves - 1))

def getprob(xy,nmoves,N,depth,visited):
if xy in visited or depth > nmoves: return 0,0
deaths = 0
x,y = xy
if xy[0] > N-1 or xy[0] < 0 or xy[1] > N-1 or xy[1] < 0:
return 1,1
moves = 1
visited.add(xy)
successors = [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]
for s in successors:
d,m = getprob(s,nmoves,N,depth+1,visited)
deaths += d
moves += m
return deaths,moves

print probabilityalive(5,5,10,10)*100

}}

def probabilityalive(x,y,nmoves,N):
	deaths,moves = getprob((x,y),nmoves,N,0,set())
	return 1 - deaths/(1.0 * (moves - 1))
	
def getprob(xy,nmoves,N,depth,visited):
	if xy in visited or depth > nmoves: return 0,0
	deaths = 0
	x,y = xy
	if xy[0] > N-1 or xy[0] < 0 or xy[1] > N-1 or xy[1] < 0:
		return 1,1
	moves = 1
	visited.add(xy)
	successors = [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]
	for s in successors:
		d,m = getprob(s,nmoves,N,depth+1,visited)
		deaths += d
		moves += m
	return deaths,moves
	
print probabilityalive(5,5,10,10)*100

#!/usr/bin/env python

from collections import defaultdict

calc_table = defaultdict(lambda : 1.0)

def p(n, steps, si, sj):

    for k in range(1, steps+1):
        for i in range(n):
            for j in range(n):
                calc_table[(n, k, i, j)] = 0
                if i-1 >= 0:
                    calc_table[(n, k, i, j)] += calc_table[(n, k-1, i-1, j)]
                if i+1 < n:
                    calc_table[(n, k, i, j)] += calc_table[(n, k-1, i+1, j)]
                if j-1 >= 0:
                    calc_table[(n, k, i, j)] += calc_table[(n, k-1, i, j-1)]
                if j+1 < n:
                    calc_table[(n, k, i, j)] += calc_table[(n, k-1, i, j+1)]
                calc_table[(n, k, i, j)] /= 4.0

    return calc_table[(n, steps, si, sj)]

if __name__ == "__main__":
    print p(4, 4, 0, 0)
    print p(4, 4, 1, 1)
    print p(4, 4, 2, 2)

Create a quadrant decision tree from the current co-ordinate with depth = n.
While you are constructing the tree, if a branch reached an out of bound condition, increase
deadly branches count by 1. And then move backwards using recursion to construct the next branch and so on. The final count of the bad branches/ the total number of branches is your probability. This is similar to what is used in gaming.

public class Island {
private int islandSize = N;
public float getSurvivalProbability(int x, int y, int n) {
if ( x < 0 || x > N - 1 || y < 0 || y > N - 1) {
return 0;
}
else if (n == 0) {
return = 1;
}
else {
return
0.25 * getSurvivalProbability(x - 1, y, n -1) +
0.25 * getSurvivalProbability(x, y - 1, n -1) +
0.25 * getSurvivalProbability(x, y + 1, n -1) +
0.25 * getSurvivalProbability(x + 1, y, n -1);
}
}
public float getDeathProbability(int x, int y, int n) {
return 1 - getSurvivalProbability(x, y);
}
}

This can be easily done using BFS. The equation I followed is as below:
ProbAlive(after N steps) = ProbAlive(after 1 step)
* ProbAlive(after 2 steps, given alive after 1 step) *
* ...
* ProbAlive(after N steps, given alive after N-1 steps)

To compute the term ProbAlive(after K steps, given alive after K-1 steps), BFS is used.
When the BFS queue has only elements with positions for kth step, sample space is the queue-size. Iterate through all elements in the queue and if position is valid, add a probability of 1/queue-size to ProbAliveCurStep. During that time, enqueue all subsequent positions with step marked as k+1. Before processing queue with positions marked as k+1, update ProbAlive = ProbAlive * ProbAliveCurStep and reset ProbAliveCurStep.

e.g. For a 4x4 Matrix, max_step 2 and initial pos 0, 0
Iteration 1:
Queue Contents: (x: 0, y: 0, step: 0)
Pop Element: (0, 0, 0)
Sample Space = 0; // Initial position is ignored for probability computation
ProbAliveCurStep = 0;
Enqueue Neighbours

Iteration 2:
Queue Contents: (1, 0, 1), (-1, 0, 1), (0, 1, 1), and (0, -1, 1)
Pop Element: (1, 0, 1) // Valid element, proceed
Sample Space = 4
ProbAliveCurStep = 0.25
Enqueue Neighbours

Iteration 3:
Queue Contents: (-1, 0, 1), (0, 1, 1) and (0, -1, 1)
Pop Element: (-1, 0, 1) // Invalid element, continue
...
...
After 13 iterations,
ProbAliveCurStep for Step 1 = 0.5, ProbAliveCurStep for Step 2 = 0.75
ProbAlive = 0.357

float getProb(int x, int y, int n, int maxSteps) {
  deque<Pos*> posQueue;
  int sampleSpace = 0, curStep = 0;
  float probAlive = 0, probAliveCurStep = 0;
  posQueue.push_back(new Pos(x, y, curStep));

  while(!posQueue.empty()) {
    // Pop current element from quque
    Pos* curPos = posQueue.front(); posQueue.pop_front();
    assert(curPos);
    assert((curPos->step == curStep) || (curPos->step == curStep + 1));

    // Update the sampleSpace if stepping to the next phase
    if (curPos->step != curStep) {
      printf("\n Step change detected from %d to %d, updating sample space  to %d", curStep, curPos->step, posQueue.size() + 1);
      sampleSpace = posQueue.size() + 1; // One element already popped.
      probAlive = probAlive ? probAlive * probAliveCurStep : probAliveCurStep;
      probAliveCurStep = 0;
      ++curStep;
    }

    // If curPos in safe zone, add to the running probability
    if (!(curPos->x < 0 || curPos->y < 0 || curPos->x >= n || curPos->y >= n)) {
      // Note: For step-0, no probability is computed.
      if (curPos->step) {
        float curProb = 1/(float)sampleSpace;
        probAliveCurStep += curProb;
      }

      // Enqueue all neighbours
      if (curPos->step < maxSteps) {
        posQueue.push_back(new Pos(curPos->x-1, curPos->y, curPos->step + 1));
        posQueue.push_back(new Pos(curPos->x+1, curPos->y, curPos->step + 1));
        posQueue.push_back(new Pos(curPos->x, curPos->y-1, curPos->step + 1));
        posQueue.push_back(new Pos(curPos->x, curPos->y+1, curPos->step + 1));
      }
    }
  }

  probAlive *= probAliveCurStep;
  return probAlive;
}

Heres my attempt, not sure if its completely sound. Any advice would be greatly appreciated :)

using System;

namespace AliveProblem
{
	class MainClass
	{
		public static int[,] island = new int[4,4];

		public static void Main (string[] args)
		{
			Console.WriteLine(probabilityofalive(1, 1, 5));
		}
		
		public static double probabilityofalive(int x, int y, int n) {
			
			//Break case
			if (n == 0) return 1;
			//corner case 
			//Top left
			if (x == 0 && y == 0) {
				return 0.5+0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
			}
			//Bottom left
			else if (x == 0 && y == island.Length-1) {
				return 0.5+0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
			}
			//Top right
			else if (x == island.Length-1 && y == 0) {
				return 0.5+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x, y-1, n-1);
			}
			//Bottom right 
			else if (x == island.Length-1 && y == island.Length-1) {
				return 0.5+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
			}
			//Left side
			else if (x == 0 && (y != 0 && y!= island.Length-1)  ) {
				return 0.25+0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1)*0.25*probabilityofalive(x+1, y, n-1);
			}
			
			//Right side 
			else if (x == island.Length-1 && (y!=0 && y!= island.Length-1)) {
				return 0.25+0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1)*0.25*probabilityofalive(x-1, y, n-1);
			}
			else if (y == 0 && ( x!= 0 && x!=island.Length-1)) {
				return 0.25+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1);
			}
			else if (y == island.Length-1 && (x != 0 && x!= island.Length-1)) {
				return 0.25+0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y-1, n-1);
				
			}
			else {
				return 0.25*probabilityofalive(x-1, y, n-1)*0.25*probabilityofalive(x+1, y, n-1)*0.25*probabilityofalive(x, y+1, n-1)*0.25*probabilityofalive(x, y-1, n-1);
			}

public class Island {
	private int[][] fields;

	public Island(int size) {
		this.fields = new int[size][size];
	}

	public boolean isInRange(int x, int y) {
		return x >= 0 && y >= 0 && x < size() && y < size();
	}

	public int size() {
		return fields.length;
	}
}

public class Walk {
	private Island island;

	Walk(Island island) {
		this.island = island;
		
	}
	
	double walk(int x, int y, int numSteps) {
		if(numSteps == 0) {
			return 1;
		}
		
		double sum = 0;

		// Go left
		if(island.isInRange(x-1, y)) {
			sum += walk(x-1, y, numSteps-1);
		}

		// Go right
		if(island.isInRange(x+1, y)) {
			sum += walk(x+1, y, numSteps-1);
		}

		// Go up
		if(island.isInRange(x, y+1)) {
			sum += walk(x, y+1, numSteps-1);
		}

		// Go right
		if(island.isInRange(x, y-1)) {
			sum += walk(x, y-1, numSteps-1);
		}
		
		return sum/4;
	}
}

public class Walk2DArray {
	private Island island;
	
	public Walk2DArray(Island island) {
		this.island = island;
	}
	
	ProbabilityContainer createArray(int numSteps) {
		Walk walk = new Walk(island);
		
		ProbabilityContainer result = new ProbabilityContainer(island.size());
		for(int i = 0; i < island.size(); i++) {
			for(int j = 0; j < island.size(); j++) {
				result.set(i, j, walk.walk(i, j, numSteps));
			}
		}
		return result;
	}
}

-----------------------------------

Unit tests:

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class Walk2DArrayTest {
	@Test
	public void test1x1_0() {
		Island island = new Island(1);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 1.0 }
		});
		assertEquals(expected, probabilityContainer);
	}

	@Test
	public void test1x1_1() {
		Island island = new Island(1);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 0.0 }
		});
		assertEquals(expected, probabilityContainer);
	}

	@Test
	public void test2x2_0() {
		Island island = new Island(2);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 1.0, 1.0},
				new double[] { 1.0, 1.0}
		});
		assertEquals(expected, probabilityContainer);
	}

	@Test
	public void test2x2_1() {
		Island island = new Island(2);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 0.5, 0.5},
				new double[] { 0.5, 0.5}
		});
		assertEquals(expected, probabilityContainer);
	}

	@Test
	public void test3x3_1() {
		Island island = new Island(3);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 0.5, 0.75, 0.5},
				new double[] { 0.75, 1.0, 0.75},
				new double[] { 0.5, 0.75, 0.5}
		});
		assertEquals(expected, probabilityContainer);
	}

	@Test
	public void test3x3_2() {
		Island island = new Island(3);
		Walk2DArray walk2DArray = new Walk2DArray(island);
		ProbabilityContainer probabilityContainer = walk2DArray.createArray(2);
		ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
				new double[] { 0.375, 0.5, 0.375},
				new double[] { 0.5, 0.75, 0.5},
				new double[] { 0.375, 0.5, 0.375}
		});
		assertEquals(expected, probabilityContainer);
	}
}

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class WalkTest {
	private static final double EPSILON = 0.0000001;

	@Test
	public void test1x1_0() {
		Island island = new Island(1);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 0);
		assertEquals(1.0, prob, EPSILON);
	}

	@Test
	public void test1x1_1() {
		Island island = new Island(1);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 1);
		assertEquals(0.0, prob, EPSILON);
	}
	
	@Test
	public void test1x1_2() {
		Island island = new Island(1);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 2);
		assertEquals(0.0, prob, EPSILON);
	}
	

	
	@Test
	public void test2x2_1() {
		Island island = new Island(2);
		Walk walk = new Walk(island);
		double prob = walk.walk(1, 1, 1);
		assertEquals(0.5, prob, EPSILON);
	}
	
	@Test
	public void test2x2_2() {
		Island island = new Island(2);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 2);
		assertEquals(0.25, prob, EPSILON);
	}
	
	@Test
	public void test3x3_2() {
		Island island = new Island(3);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 2);
		assertEquals(0.375, prob, EPSILON);
	}
	
	@Test
	public void test2x2_3() {
		Island island = new Island(2);
		Walk walk = new Walk(island);
		double prob = walk.walk(0, 0, 3);
		assertEquals(0.125, prob, EPSILON);
	}
}

public class IslandWanderSurvivalProbability {

	static double survivalProbability(int x, int y, int N, int n){
		if(x < 0 || x >= N || y < 0 || y >= N){
			return 0;
		}
		
		double p[][] = new double[N][N];
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				p[i][j] = 0.0;
			}
		}
		p[x][y] = 1.0;
		
		p = computeStateSurvivalProbabilities(p, N, n);
		double pSum = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				pSum += p[i][j];
			}
		}
		
		if(n < 3){
			for(int i = 0; i < N; i++)
				System.out.println(Arrays.toString(p[i]));
		}

		return pSum;
	}
	
	static double[][] computeStateSurvivalProbabilities(double p[][], int N, int n){
		double pUptoNMinus1[][] = p;
		
		if(n == 0){
			return p;
		} else if(n > 1){
			pUptoNMinus1 = computeStateSurvivalProbabilities(p,N,n-1);
		}
		
		double pNextStep[][] = new double[N][N];
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				pNextStep[i][j] = 0.0;
			}
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(i+1 < N){
					pNextStep[i+1][j] += 0.25*pUptoNMinus1[i][j];
				}
				if(j+1 < N){
					pNextStep[i][j+1] += 0.25*pUptoNMinus1[i][j];
				}
				if(i-1 >=0){
					pNextStep[i-1][j] += 0.25*pUptoNMinus1[i][j];
				}
				if(j-1 >=0){
					pNextStep[i][j-1] += 0.25*pUptoNMinus1[i][j];
				}
			}
		}
		
		return pNextStep;
	}
	
	public static void main(String[] args) throws Exception{
	
		for(int n = 0; n < 20; n++){
			double pSurvival = survivalProbability(1,1,3,n);
			System.out.println(n + "\t" + pSurvival);
		}
	}
}

Inspired by you all, I think 3-dimensional DP is trival!

double probabilityAliveDP(int x, int y, int N, int step){
	if(N==0 || x<0 ||x>=N || y<0 || y>=N ) return 0;
	vector<vector<vector<double> > > dp(N+2, vector<vector<double> >(N+2, vector<double>(step+1, 0)));
	for(int i=1;i<N+1;i++)
		for(int j=1; j<N+1; j++)
			dp[i][j][0] = 1.0;

	for(int i=1;i<=step;i++){
		for(int r = 1; r < N+1; r++){
			for(int c = 1; c < N+1; c++){
				dp[r][c][i] = 0.25*(dp[r-1][c][i-1]+dp[r+1][c][i-1]+dp[r][c-1][i-1]+dp[r][c+1][i-1]);
			}
		}
	}
	return dp[x+1][y+1][step];
}

My idea is a 3-dimensional dp

double probabilityAliveDP(int x, int y, int N, int step){
	if(N==0 || x<0 ||x>=N || y<0 || y>=N ) return 0;
	vector<vector<vector<double> > > dp(N+2, vector<vector<double> >(N+2, vector<double>(step+1, 0)));
	for(int i=1;i<N+1;i++)
		for(int j=1; j<N+1; j++)
			dp[i][j][0] = 1.0;

	for(int i=1;i<=step;i++){
		for(int r = 1; r < N+1; r++){
			for(int c = 1; c < N+1; c++){
				dp[r][c][i] = 0.25*(dp[r-1][c][i-1]+dp[r+1][c][i-1]+dp[r][c-1][i-1]+dp[r][c+1][i-1]);
			}
		}
	}
	return dp[x+1][y+1][step];
}

public static double probabilityOfAlive(int x,int y, int step, int n) {  
      if (x<0 || y<0 || x>=n || y>=n || (n==1 && step==1)) return 0;  
      if (step == 0) return 1;  
      double[][][] probTable = new double[n][n][step+1];  
      int sp = 0;  
      // init for step=1  
      for (int i=0; i<n; ++i) {  
        for (int j=0; j<n; ++j) {  
          probTable[i][j][sp] = 0;  
          if (i>0) probTable[i][j][sp] = 1;  
          if (j>0) probTable[i][j][sp] = 1;  
          if (i+1<n) probTable[i][j][sp] = 1;  
          if (j+1<n) probTable[i][j][sp] = 1;  
        }  
      }  
      // calculate with DP  
      for(sp=1;sp<=step;sp++) {
          for (int i=0; i<n; ++i) {  
              for (int j=0; j<n; ++j) {  
                  probTable[i][j][sp] = 0;  
                  if (i>0) probTable[i][j][sp] += 0.25*probTable[i-1][j][sp-1];  
                  if (j>0) probTable[i][j][sp] += 0.25*probTable[i][j-1][sp-1];  
                  if (i+1<n) probTable[i][j][sp] += 0.25*probTable[i+1][j][sp-1];  
                  if (j+1<n) probTable[i][j][sp] += 0.25*probTable[i][j+1][sp-1];  
                  if (sp==step && i==x && j==y) return probTable[x][y][sp];  
              }  
          }  
      }  
      return probTable[x][y][step];  
    }

Wouldn't the following code be sufficient enough?

public class ProbabilityOfAlive
{
	public final int N = 5;
	
	public static void main(String[] args)
	{
		ProbabilityOfAlive obj = new ProbabilityOfAlive();
		float result = obj.probabilityOfAlive(4, 4, 2);
		System.out.println("Result: "+result);
	}
	
	public float probabilityOfAlive(int x, int y, int n)
	{
		// Last step
		if(n == 0)
		{
			if(x>=0 && x<N && y>=0 && y<N)
				return 1;
			else
				return 0;
		}
		
		// Dies
		else if(x<0 || x>=N || y<0 || y>=N)
		{
			return 0;
		}
		
		// Alive
		else
		{
			float up = probabilityOfAlive(x, y+1, n-1);
			float down = probabilityOfAlive(x, y-1, n-1);
			float left = probabilityOfAlive(x-1, y, n-1);
			float right = probabilityOfAlive(x+1, y, n-1);
			return 0.25f*(up+down+left+right);
		}
			
	}

Here's a simple Python solution with memorization

mem = None

def prob(x,y,n,N):
    global mem
    if mem is None:
        mem = [[[-1.0 for a in range(n+1)] for b in range(N)] for c in range(N)]
    if x < 0 or x >= N or y < 0 or y >= N:
        return 0.0
    if n == 0:
        return 1.0
    if mem[x][y][n] > 0:
        return mem[x][y][n]
    res =  (0.25*prob(x+1,y,n-1,N) +
            0.25*prob(x,y+1,n-1,N) +
            0.25*prob(x-1,y,n-1,N) +
            0.25*prob(x,y-1,n-1,N))
    mem[x][y][n] = res
    return res

print prob(3,3,50,20)

public static double islandSurvive(int x, int y, int N, int steps) {
		double survs = (double) islandHelp(x,y,N,steps);
		return survs / Math.pow(4.0, (double) steps);
	}
	
	public static int islandHelp(int x, int y, int N, int rem) {
		if (x > N-1 || x < 0 || y < 0 || y > N-1) {
			return 0;
		}
		if (rem == 0) { return 1; }
		else {
			return islandHelp(x+1,y,N,rem-1) + 
				   islandHelp(x-1,y,N,rem-1) + 
				   islandHelp(x,y-1,N,rem-1) + 
				   islandHelp(x,y+1,N,rem-1);
		}
	}

public static double islandSurvive(int x, int y, int N, int steps) {
		double survs = (double) islandHelp(x,y,N,steps);
		return survs / Math.pow(4.0, (double) steps);
	}
	
	public static int islandHelp(int x, int y, int N, int rem) {
		if (x > N-1 || x < 0 || y < 0 || y > N-1) {
			return 0;
		}
		if (rem == 0) { return 1; }
		else {
			return islandHelp(x+1,y,N,rem-1) + 
				   islandHelp(x-1,y,N,rem-1) + 
				   islandHelp(x,y-1,N,rem-1) + 
				   islandHelp(x,y+1,N,rem-1);
		}
	}

Here is an O(1) solution:

float probabilityofalive(int x,int y, int n) {
  return math.pow(1.0 - 1.0 / x, n);
}

Let the simplicity of the answer sink in.

Given a square matrix of size NxN, for any single direction, the probability of dying is 1/N -- that is to say, those on an edge will go into the water. There are four possible directions, each with the same probability, so 4*((1/4)(1/N)) still equals 1/N chance of death on any given turn, or (1 - 1/N) chance of survival.

To survive X times, we raise this probability to that power: (1 - 1/N)^X

Again, look at the code above. Not all problems need to be complex. If you get this problem, don't go right for the formula. Show a 1x1 grid and convince someone that the odds of survival are 0. Repeat this for a 2x2 and a 3x3. Do it for just one step. Why can we just multiply probabilities for subsequent steps? It's because there is an equal probability of landing on any square after a given round. This means that each round is independent, and we can reach back to our statistics classes wherein we learn the the probabilities of independent events can be multiplied to come up with the combined probability.