Description
有一只坏了的机器人站在一个(n imes m)的网格里，初始位置在((x,y))。现在每个单位时间内它会随机选左右下三个方向走，如果它随机的方向会走出网格就不会往这个方向走。当然这个机器人也可能原地停留一个单位时间。求机器人走到第(n)行的期望时间。
满足(n,mle 10^3,1le xle n,1le yle m)。
Solution
考虑期望DP。
经过变换可使得(x=1)。
正着不好做，不妨倒过来，计算从最后一行任意位置到达((1,y))的期望时间。设(f_{x,y})是到达((x,y))的期望时间。
不妨假设我们已经计算完了到达第(i-1)行每一个位置的期望时间(f_{i-1,1},f_{i-1,2},cdots,f_{i-1,m})。现在记(x_1,x_2,cdots,x_m)为(f_{i,1},f_{i,2},cdots,f_{i,m})，(t_1,t_2,cdots,t_m)为(f_{i-1,1},f_{i-1,2},cdots,f_{i-1,m})。
容易列出状态转移方程：
[egin{cases}&x_1=frac{1}{3}(x_1+x_2+t_1)+1\&x_i=frac{1}{4}(x_{i-1}+x_i+x_{i+1}+t_i)+1;;;;;;(1<i<m)\&x_m=frac{1}{3}(x_{m-1}+x_m+t_m)+1end{cases}
]
整理得：
[egin{cases}&2x_1-x_2=t_1+3\&3x_i-x_{i-1}-x_{i+1}=t_i+4;;;;;;(1<i<m)\&2x_m-x_{m-1}=t_m+3end{cases}
]
可以发现这个方程并没有办法直接DP。
所以不妨考虑解方程。将上述方程写成增广矩阵形式如下：
[left[egin{array}{c|c}egin{matrix}2 & -1\-1 & 3 & -1\& -1 & 3 & -1\&& cdots & cdots & cdots\&&& -1 & 3 & -1\&&&& -1 & 3 & -1\&&&&& -1 & 2end{matrix}&egin{matrix}t_1+3\t_2+4\t_3+4\cdots\t_{m-2}+4\t_{m-1}+4\t_m+3end{matrix}end{array}
ight]
]
逐行消元。假设我们已经消掉了第(i-1)行，要消第(i)行，矩阵局部如下：
[left[egin{array}{c|c}egin{matrix}1 & -A\-1 & 3 & -1end{matrix}&egin{matrix}y_{i-1}\y_iend{matrix}end{array}
ight]
]
两式相加得：
[left[egin{array}{c|c}egin{matrix}1 & -A\& 3-A & -1end{matrix}&egin{matrix}y_{i-1}\y_{i-1}+y_iend{matrix}end{array}
ight]
]
将主对角线上的数消成(0)：
[left[egin{array}{c|c}egin{matrix}1 & -A\& 1 & -frac{1}{3-A}end{matrix}&egin{matrix}y_{i-1}\frac{y_{i-1}+y_i}{3-A}end{matrix}end{array}
ight]
]
我们就能得到迭代式(A'=frac{1}{3-A})。消元完成后反解回去即可。
处理完边界条件后，容易写出代码。
Code
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y;
double A[1001],B[1001],F[1001][1001];
int main(){
scanf("%d%d%d%d",&n,&m,&x,&y);
n-=x-1;
if(m==1||m==2){printf("%d
",(n-1)*(m+1));return 0;}
A[1]=0.5;
for(int i=2;i<m;i++)A[i]=1/(3-A[i-1]);
for(int i=n-1;i>=1;i--){
B[1]=(F[i+1][1]+3)/2;
for(int j=2;j<m;j++)B[j]=(B[j-1]+F[i+1][j]+4)*A[j];
F[i][m]=(B[m-1]+F[i+1][m]+3)/(2-A[m-1]);
for(int j=m-1;j>=1;j--)F[i][j]=B[j]+F[i][j+1]*A[j];
}
printf("%.10lf
",F[1][y]);
}