（提醒：原题面是 \(m\) 行 \(n\) 列，这里改成了 \(n\) 行 \(m\) 列）
首先很好想到设 \(dp_{u,v}\) 为 \((u, v)\) 的期望步数
\(dp_{u, v} = \begin{cases}\sum_{i=1}^4 dp_{u + du_i,v + dv_i}\times p_i& (u \not = n \operatorname{or} v \not = m)\\ 0& (u = n \operatorname{and} v = m)\end{cases}\)
很明显有环跑个高斯消元，\(dp_{1,1}\) 即为答案的值
然后是不是以为就过了，嘻嘻，\(1\le n, m\le 40\)，\(O((nm)^3)\) T 飞
发现对于“从上至下，从左至右”这种标记法，对 \(id_{x, y}\) 来说与其相邻的 \(4\) 个点分别为 \(id_{x, y} - m, id_{x, y} - 1, id_{x, y} + 1, id_{x, y} + m\)，相差最大也只有 \(m\)
那就很好办了，消元的时候对于每个点，只往下找 \(m\) 行，也只往右找 \(m\) 列，因为只有这部分才能消，特别处理以下方程组的和即可，时间复杂度 \(O(nm^3)\)
然后是不是以为就过了，嘻嘻，这题卡精度，而且是往低了卡，而且卡的很恶心
如果完全没问题还是 WA 了建议照着代码重写高斯消元的写法，写的时候可能会觉得这个高斯消元的精度低得离谱，但只有这样能过（悲
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const int N = 40 + 5, K = 4;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int id[N][N];
double g[N * N][N * N];
int n, m;
void solve() {
int nm = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
id[i][j] = ++nm;
}
}
for (int i = 1; i <= nm; i++) {
for (int j = 1; j <= nm + 1; j++) {
g[i][j] = 0.0;
}
}
for (int i = 1; i <= nm; i++) {
g[i][i] = g[i][nm + 1] = 1.0;
}
for (int h = 0; h < 4; h++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
double p;
scanf("%lf", &p);
int vi = i + dx[h], vj = j + dy[h];
if (vi < 1 || vj < 1 || vi > n || vj > m) {
continue;
}
g[id[i][j]][id[vi][vj]] = -p;
}
}
}
g[id[n][m]][id[n - 1][m]] = g[id[n][m]][id[n][m - 1]] = g[id[n][m]][nm + 1] = 0.0;
for (int i = 1; i <= nm; i++) {
/*
int h = i;
for (int j = i + 1; j <= min(i + m, nm); j++) {
if (fabs(g[j][i]) > fabs(g[h][i])) {
h = j;
break;
}
}
swap(g[i], g[h]);
*/
for (int j = i; j <= min(i + m, nm); j++) {
if (fabs(g[j][i]) > 0) {
swap(g[i], g[j]);
break;
}
}
g[i][nm + 1] /= g[i][i];
for (int j = min(i + m, nm); j >= i; j--) {
g[i][j] /= g[i][i];
}
for (int j = i + 1; j <= min(i + m, nm); j++) {
g[j][nm + 1] -= g[j][i] * g[i][nm + 1];
for (int k = min(i + m, nm); k >= i; k--) {
g[j][k] -= g[j][i] * g[i][k];
}
}
}
for (int i = nm; i >= 1; i--) {
for (int j = i + 1; j <= min(i + m, nm); j++) {
g[i][nm + 1] -= g[i][j] * g[j][nm + 1];
}
}
printf("%.6lf\n", g[1][nm + 1]);
return ;
}
int main() {
for (; ~ scanf("%d%d", &n, &m) && n && m; ) {
solve();
}
return 0;
}