Branching factor of a pathfinding procedure

Question

I have a $n\times n$ matrix with $n'$ elements randomly distributed across the matrix cells, the rest of them can be considered to be empty. With this initial state, I randomly select a $(i, j)$ position in the matrix (supposing I can only pick empty cells) in order to place a new element inside and invoke a certain procedure:

Procedure(int i, int j, int up) {
        if (not in_range(i, j) or not empty(i, j) or visited(i, j)) {
            return false;
        }

        visited(i, j) = true
        if (not up) {
            if (i == (grid.length - 1)) {
                return true;
            }

            for (neighbor k in { { 1, 0 }, { 1, -1 }, { 1, 1 }, { 0, -1 }, { 0, 1 } }) {
                if (Procedure(k[0] + i, k[1] + j, up)) {
                    return true;
                }
            }

        } else {
            if (i == 0) {
                return true;
            }

            //Opposite for up neighbors
        }
        return false;
    }

The procedure aims to detect whether there exists or not a path from the input $(i, j)$ position of the matrix to the top/bottom row, depending on the input value up. For simplicity, we can only focus on the case when it detects paths to the bottom row and assume $visited$ to be another binary matrix representing each cell's visited state, and $grid$ to be the matrix we are working with. Additionally, the function in_range simply returns wether the $(i, j)$ coordinates are inside or outside of the matrix.

Now, the problem comes when trying to analyze its time complexity. At first glance, we can try to create a recurrence relation that encapsulates the times Procedure calls itself, the amount of work each call performs, and the change in the problem size for successive future calls.

$T(i, j)=P\times (T(i, j-1)+T(i, j+1)+T(i-1, j)+T(i-1, j-1)+T(i-1, j+1))$

Assume the base case to be $T(0, j)$, meaning the function has reached the edge row and returns true.

However, when trying to solve the recurrence, we still need to find the probability factor $P$ that affects the number of calls the function performs. This term depends on the probability of a neighbor to be traversable, which we can calculate easily as the amount of elements in matrix divided by $n^2$, since they are all randomly distributed, and the probability of a neighbor to be unvisited by the algorithm, which is much harder to calculate.

The question is: Is there an alternative way to calculate the branching factor for this recurrence relation without having to calculate the probability component of visited for every neighbor? Also, as the branching factor affects which subproblem call the procedure will take, is there any way to reflect this fact on the recurrence relation?

Finally, in the worst case, due to its similarity with the Depth First Search algorithm, coult its time complexity be equivalent to $O(V+E)$ (with the corresponding values of V and E being the interpretation of the matrix as a fully connected graph)?