坏掉的机器人

AcWing-290-坏掉的机器人

分析

见《进阶指南》第298页。

实现

#include <iostream>
using namespace std;

const int N = 1010;
int n, m, x, y;
double f[N][N], a[N][N];

void Gauss () {
    for (int i = 1; i <= m; ++ i) {
        double b = a[i][i];
        a[i][i] /= b, a[i][i + 1] /= b;
        if (i <= m - 1) a[i][m + 1] /= b;

        double c = a[i + 1][i];
        int d[3] = { i, i + 1, m + 1 };
        for (int j = 0; j < 3; ++ j)
            a[i + 1][d[j]] -= c * a[i][d[j]];
    }
    for (int i = m; i >= 1; -- i) {
        a[i - 1][m + 1] -= a[i - 1][i] * a[i][m + 1];
        a[i - 1][i] -= a[i - 1][i] * a[i][i];
    }
}

int main () {
    scanf("%d%d%d%d", &n, &m, &x, &y);

    if (m == 1) {
        printf("%.4lf", 2.0 * (n - x));
        return 0;
    }
    for (int i = n - 1; i >= x; -- i) {
        a[1][1] = 2.0 / 3, a[1][2] = -1.0 / 3, a[1][m + 1] = f[i + 1][1] / 3 + 1;
        a[m][m - 1] = -1.0 / 3, a[m][m] = 2.0 / 3, a[m][m + 1] = f[i + 1][m] / 3 + 1;
        for (int j = 2; j <= m - 1; ++ j) {
            a[j][j - 1] = -1.0 / 4;
            a[j][j] = 3.0 / 4;
            a[j][j + 1] = -1.0 / 4;
            a[j][m + 1] = f[i + 1][j] / 4 + 1;
        }
        Gauss();
        for (int j = 1; j <= m; ++ j)
            f[i][j] = a[j][m + 1];
    }
    printf("%.4lf", f[x][y]);
    return 0;
}