坏掉的机器人
分析
见《进阶指南》第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;
}