import java.text.DecimalFormat;

import java.util.*;

public class BobProblem{

public static double bob2(int[][] arr,int i,int j,int K){

int N = arr.length;

int M = arr[0].length;

if(i>=N || i<0 || j>=M || j<0){

return 1.0;

}

int[][][] dp = new int[N][M][K+1];

for (int r=0; r<N; r++) {

for (int c=0; c<M;c++ ) {

for (int s=0; s<=K; s++) {

dp[r][c][s] =-1;

}

}

}

return process2(arr,i,j,K,dp)/Math.pow(4,K);

}

public static int process2(int[][] arr, int curR,int curC,int rest,int[][][] dp){

if(curR == arr.length || curR <0 || curC == arr[0].length || curC<0){

return 0;

}

if(dp[curR][curC][rest]!=-1 && rest>=0){

return dp[curR][curC][rest];

}

if(rest == 0){

return 1;

}

int ans=

process2(arr,curR+1,curC,rest-1,dp)+

process2(arr,curR-1,curC,rest-1,dp)+

process2(arr,curR,curC+1,rest-1,dp)+

process2(arr,curR,curC-1,rest-1,dp);

dp[curR][curC][rest]=ans;

return ans;

}

public static void main(String[] args){

int N = 15;

int[][] arr= new int[N][N];

DecimalFormat df = new DecimalFormat("0.000000000");

System.out.println("P = "+df.format(bob2(arr,4,4,15)));

}

}