(This is a question inspired by and abstracted from various adventure computer games involving navigating a map of rooms.)
Consider a grid of squares. The grid has total width W and total height H. You start on an entrance square in the lower-left or southwestern corner. Your goal is to reach an exit square in the fewest steps possible, where a "step" means to move orthogonally (vertically or horizontally only; diagonal moves are not allowed) into an adjacent square.
If the exit square is in the top-right or northeast corner, this would take W + H - 2 steps: you would move W - 1 steps to the right/east, and then H - 1 steps to the top/north to reach the exit square, for a total of W + H - 2 steps.
But, there is a twist: whenever you take a step, there is a constant probability P that you will be teleported to a random square instead of to the square you were trying to step to.
(Note of clarification: Many of the games I was playing seem to have additional code preventing the destination of teleportation from being one or more of the following types: (1) the square you are stepping from (2) the square you are stepping to (3) the entrance square (4) the exit square. Which types are avoided varies depending on the game. The math is probably easier not having to deal with these exceptions. I'd be interested in all types of answers, both those with or without dealing with any of these exceptions.)
The two parts to my question:
(1) In terms of W, H, and P, what is the expected number of steps to reach that exit square in the top-right corner?
(2) Same question, but now W and H are both guaranteed to be odd, and the exit square is now the center square of this grid rather than the top-right/northeast square of this grid.
I am going to assume that, at each step, the dungeon crawler is allowed to decide in which direction she is going to move. This simplifies things, since now the randomness is only in being teleported, and this assumption aligns with your answer in the $P=0$ case.
The dungeon crawler will always choose to step in a direction that would bring her closer to the exit. The number of steps it would take to get from room $(i,j)$ to the exit room $(W,H)$ is $d =W+H-i-j$. Then, with probability $(1-P)$, the dungeon crawler will be at distance $d-1$ from the exit, and with probability $P$ she will be at a random distance from the exit. The starting room, which is the room furthest away from the exit, is at distance $W+H-2$ from it.
Let $e_d$ be the expected number of steps the dungeon crawler has to take in order to reach the exit, given that she is distance $d$ from the exit currently. Importantly, this does not depend on which room she is in, only the distance. Our goal is to determine $e_{W+H-2}$.
We can write a recurrence relation for $e_d$ as follows: \begin{equation} e_d = (1-P)(1+e_{d-1}) + P \sum_{k=0}^{W+H-2} q_k e_k, \end{equation} where $q_k$ is the probability that, when selecting a room uniformly at random, you choose one distance $k$ away from the exit (we will compute this later).
We also know that $e_0 =0$, i.e. if you are at the exit you do not need to take any steps away from the exit. So we can rearrange the equation for $e_1$ to be: \begin{equation} (1-Pq_1)e_1 = (1-P) + P \sum_{k=2}^{W+H-2} q_k e_k. \end{equation} Now, instead of solving for each $e_d$, the problem simplifies if we try to solve instead for $a_d := e_d/e_1$, so $e_d = a_k e_1$. We know that $a_1=1$, and also: \begin{align} e_d = a_d e_1 &= (1-P) + (1-P)a_{d-1}e_1 + P \sum_{k=1}^{W+H-2} q_k e_k \\ &=(1-P ) \Big((1-P)a_{d-1} + (1-Pq_1) - (1-Pq_1) \Big) e_1 + P \sum_{k=1}^{W+H-2} q_k e_k \\ &= (1-P) + \Big((1-P)a_{d-1} + (1-Pq_1)\Big)e_1 - \left ((1-P) - P \sum_{k=2}^{W+H-2} q_k e_k \right ) + P \sum_{k=1}^{W+H-2} q_k e_k \\ &= ((1-P)a_{d-1} + 1- Pq_1)e_1 + Pq_1 e_1 \\ &= ((1-P)a_d + 1)e_1 \end{align} So we have the recurrence relation: \begin{equation} a_{d+1} = (1-P)a_d + 1 \end{equation} Importantly, this does not depend on $q_d$! We can solve this explicitly, with the inital condtion $a_1=1$, say, by using the ansatz $a_d = A(1-P)^d + B$. We get: $$a_d = \frac{ 1 - (1-P)^d }{P}$$ when $P \neq 0$ (if $P=0$ then clearly $a_d = d$). With this, we can write an expression for $e_1$: $$\tag{1}\label{1} e_1 = \frac{1-P}{1-\sum_{k=1}^{W+H-2} q_k (1-(1-P)^k)}$$ and then $$\tag{2}\label{2} e_{W+H-2} = \frac{(1-(1-P)^{W+H-2})}{P}e_1.$$
Now all we have left to do is determine $q_d$, this follows from a simple counting argument. Without loss of generality, we assume that $H \leq W$, i.e. that the dungeon is wider than it is tall (otherwise, we can swap $H$ and $W$). Then, for $d=0,\dots, W+H-2$, the number of rooms $r_d$ that are distance $d$ from the exit is \begin{equation} \tag{3}\label{3} r_d = \begin{cases} d+1 &, d = 0,\dots, H-1\\ H &, d= H, \dots, W-1 \\ H - 1 - (d-W) &, d= W, \dots, W+H-2 \end{cases} \end{equation} and then $q_d = r_d/(WH)$. Altogether, you can combine \eqref{1}, \eqref{2} and \eqref{3} to obtain an admittedly, very ugly, formula for the expected number of steps to reach the exit. I don't imagine that this can be simplified very much, as the form of $q_d$ is very messy, but maybe it simplifies in the case of a square.
In your second case, where $W$ and $H$ are odd and the exit room is in the centre, the exact same computations apply. This time however, you start of at distance $((W+H)/2-1)$ from the exit, and the formula for the $q_d$ would be different. This can still be computed by hand, though. In any case, the expression \eqref{1} still holds, with the upper bound and the $q_d$ replaced.