CodeForces

Luogu

分析

设 $f_{i, j}$ 表示 $(i,j)$ 到最后一排的移动步数的期望。显然有转移

$$
\begin{aligned}
f[i][1] & =\frac{1}{3}(f[i][1]+f[i][2]+f[i-1][1])+1 \\
f[i][m] & =\frac{1}{3}(f[i][m]+f[i][m-1]+f[i-1][m])+1 \\
f[i][j]=\frac{1}{4}(f[i][j]+f[i][j-1]+f[i][j+1]+f[i-1][j] (1 < j < m)
\end{aligned}
$$

对于每行，列与列之间的转移有后效性，高斯消元即可。但是这是一个 band-matrix，所以可以 $\mathcal{O}(m)$ 消元。

注意特判$m=1$的情况。

代码

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

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m,X,Y;
double f[1010][1010];

double a[1010][1010];
double b[1010];

inline void Build(int R) {
    if (m==1) {
        a[1][1]=-1.0/2.0;
        b[1]=-f[R+1][1]/2.0-1;
        return;
    }
    a[1][1]=a[m][m]=-2.0/3.0,a[1][2]=a[m][m-1]=1.0/3.0;
    b[1]=-f[R+1][1]/3.0-1,b[m]=-f[R+1][m]/3.0-1;
    for (re int i=2;i<m;i++) {
        a[i][i-1]=a[i][i+1]=1.0/4.0,a[i][i]=-3.0/4.0;
        b[i]=-f[R+1][i]/4.0-1;
    }
}

inline void Guass(int R) {
    for (re int i=1;i<m;i++) {
        double rate=a[i+1][i]/a[i][i];
        a[i+1][i]-=rate*a[i][i];
        a[i+1][i+1]-=rate*a[i][i+1];
        b[i+1]-=rate*b[i];
    }
    f[R][m]=b[m]/a[m][m];
    for (re int i=m-1;i>=1;i--) f[R][i]=(b[i]-f[R][i+1]*a[i][i+1])/a[i][i];
}

int main() {
    n=read(),m=read(),X=read(),Y=read();
    for (re int i=n-1;i>=X;i--) { Build(i); Guass(i); }
    printf("%.10f\n",f[X][Y]);
    return 0;
}