由于是平面图，所以边数不超过 $3n-6$。设 $p_i$ 为第 $i$ 步走到 $n$ 的概率，则 $p_0,p_1,\ldots$ 是不超过 $n$ 阶的线性递推数列，用 BM 算法求出递推式，然后将其生成函数表示为 $P(x)=\frac{Q(x)}{R(x)}$。

要求的期望即为 $P'(1)=(\frac{Q(x)}{R(x)})'\mid _{x=1}=\frac{Q'(1)R(1)-R'(1)Q(1)}{R^2(1)}$。时间复杂度 $O(n^2)$。