即将 AFO 的老年选手

题解 P6899 【[ICPC2014 WF]Pachinko】

2021-02-24 17:08:34


设 $f_{i, j}$ 为能够到达 $(i, j)$ 的概率,可以列出一个 $n\times m$ 元方程组。然而直接解时空都无法承受。

不妨把所有格子按照从上到下、从左往右的顺序编号,这样子矩阵是一个长度为 $m$ 的带状矩阵。

因从我们只需要对每行保存 $2m$ 个值,消元时也只需要往下消 $m$ 行再回代就可以了。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 10000 + 10, M = 20 + 10;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
const double eps = 1e-9;

int n, m, p[4]; // u, d, l, r
char s[N][M];
int L[N * M];
double A[N * M][M << 1], B[N * M];

int id(int x, int y) { return x * m + y; }
#define A(x, y) A[x][y - L[x]]

void Gauss() {
    for (int i = 0; i < n * m; ++i) {
        if (fabs(A(i, i)) < eps) continue;
        for (int j = i + 1; j <= i + m && j < n * m; ++j) {
            double t = A(j, i) / A(i, i);
            for (int k = i; k <= i + m && k < n * m; ++k) A(j, k) -= t * A(i, k);
            B[j] -= t * B[i];
        }
    }
    for (int i = n * m - 1; ~i; --i) {
        for (int j = i + 1; j <= L[i] + 2 * m && j < n * m; ++j)
            B[i] -= A(i, j) * B[j];
        B[i] = fabs(A(i, i)) < eps ? 0 : (B[i] / A(i, i));
    }
}

int main() {
    m = read(), n = read();
    for (int i = 0; i < 4; ++i) p[i] = read();
    for (int i = 0; i < n; ++i) scanf("%s", s[i]);
    for (int i = 0; i < n * m; ++i) L[i] = std::max(0, i - m);
    int c0 = 0;
    for (int i = 0; i < m; ++i) c0 += (s[0][i] == '.');
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            int u = id(i, j);
            if (s[i][j] == '.') {
                A(u, u) = 1;
                if (!i) B[u] = 1.0 / c0;
                int sp = 100;
                for (int d = 0; d < 4; ++d) {
                    int x = i + dx[d], y = j + dy[d];
                    if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == 'X') sp -= p[d];
                }
                for (int d = 0; d < 4; ++d) {
                    int x = i + dx[d], y = j + dy[d], v = id(x, y);
                    if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == 'X') continue;
                    A(v, u) = -1.0 * p[d] / sp;
                }
            }
            if (s[i][j] == 'X') A(u, u) = 1;
            if (s[i][j] == 'T') A(u, u) = 1;
        }
    Gauss();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (s[i][j] == 'T') printf("%.9lf\n", B[id(i, j)]);
    return 0;
}