Since we can move each of the four sides from the current position (i,j) with equal probability, which means we have 1/4 chances for each move, we will calculate the overall probability with the help of the Depth-first search approach based on recursion.

We will simply return 0 if the position is out of index bound and we return 1 is we have completed all moves K.

We will use two functions as issafe function which will return true or false depending upon the position, if we are under the index bound of the matrix then it returns true otherwise false.

Another function issolve function which will return the probability, the base condition of the recursive call is if we are not in a safe location then it would simply return 0 and if we have exhausted all our moves then it would return 1. Other possible causes are the movement in all four directions for that we used a variable p.

Time Complexity for the above approach is Exponential.

Space Complexity for the above approach is Constant.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//it return true if we are under
//valid index bound otherwise false.
bool issafe(ll x, ll y, ll n, ll m)
{
    //under valid index bound.
    if (x >= 0 and x < n and y >= 0 and y < m)
        return true;
    else //out of index bound
        return false;
}

//solve function which will find
//overall probability for K moves.
double solve(ll x, ll y, ll n, ll m, ll k)
{
    //if index range is out of bound.
    if (issafe(x, y, n, m) == false)
        return 0;

    //if all K moves have been completed.
    if (k == 0)
        return 1;

    //initialize probability variable p
    //with 0 value.
    double p = 0;

    //here .25 is multiplied with each move
    //because of equal probable movement.

    //perform down movement.
    p += solve(x + 1, y, n, m, k - 1) * .25;
    //perform up movement.
    p += solve(x - 1, y, n, m, k - 1) * .25;
    //perform right movement.
    p += solve(x, y + 1, n, m, k - 1) * .25;
    //perform left movement.
    p += solve(x, y - 1, n, m, k - 1) * .25;

    return p;
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of matrix: ";
        ll N, M, K;
        cin >> N >> M;

        ll x, y;
        cout << "Enter initial position: ";
        cin >> x >> y;

        cout << "Enter moves: ";
        cin >> K;

        cout << "Final Probability: ";
        cout << solve(x, y, N, M, K) << "\n";
    }
 
    return 0;
}

Output:

Enter number of test cases: 2
Enter size of matrix: 3 4
Enter initial position: 1 2
Enter moves: 3
Final Probability: 0.609375
Enter size of matrix: 5 5 
Enter initial position: 1 1
Enter moves: 2
Final Probability: 0.875