Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.
What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?
We can travel to 4 neighbors.
that is ( i , j+1 ), ( i , j-1 ), ( i-1, j ), ( i+1 , j ) if they are inside the matrix.
If there are only 3 neighbors which are inside the matrix then the probability with which we will go to that neighbor is 1/3(for each of the three).
How to solve this problem? I am able to find the solution for exactly k steps.
for exactly k steps problem, I make a matrix, dp[m][n][k+1]; initial all values are zero
except dp[x][y][0]=1;
dp[a][b][q]= weighted average of probablity of neighbours.
for example dp[0][0][4] = 0.5 * dp[1][0][3] + 0.5 * dp[0][1][3];
answer will be dp[i][j][k];