UVA 12177 First Knight

（提醒：原题面是 \(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;
}