一个 $5\times 5$ 的矩阵，初始时有一只蚂蚁位于矩阵中心点，矩阵底层（第五行）每一个单元格上各放有一个种子。现在蚂蚁每次将会随机朝某一个相邻单元格（四相邻）移动，每当蚂蚁遇到一个种子时，它会拿起种子（如果已经拿了一个种子就不能再拿了），当蚂蚁将种子搬运到第一行的某个空单元格后就会将种子放下。当第一行放满种子后，蚂蚁将会停止移动。询问蚂蚁的期望移动步数。

很明显是一个吸收型马尔可夫链的问题，具体信息请参考这篇文章，本文将直接印用结论。本题中的吸收态很明显是：蚂蚁将所有种子都搬运到第一行，瞬态则是其他所有状态。我们需要做的就是构造出吸收型马尔可夫链的规范矩阵，这需要一系列比较麻烦的分析和建图。

主要分两类讨论：

1. 蚂蚁拿着种子。
2. 蚂蚁不拿种子。

蚂蚁拿着种子时，$5\times 5$ 的矩阵中还剩下 $4$ 个种子，这 $4$ 个种子分布在第一行和第五行，蚂蚁可能位于矩阵中的任意位置，但是如果蚂蚁在第一行，那么它所在的单元格必定已经有种子了。

蚂蚁不拿种子时，$5\times 5$ 的矩阵中还剩下 $5$ 个种子，这 $5$ 个种子也分布在第一行和第五行，蚂蚁也可能位于矩阵中的任意位置，但是如果蚂蚁在第五行，那么它所在的单元格必定没有种子。

搜索出所有状态之后即可建图求转移矩阵，由于状态的总数一共 $10270$ 种，因此我们需要构造一个巨大的矩阵，矩阵求逆的复杂度是 $O(N^3)$ ，所以算法复杂度高达惊人的 $10^{12}$ ，跑半个小时左右才能跑完。

#include <bits/stdc++.h>
using namespace std;
#define db double
constexpr int SIZE = 11111;
db a[SIZE][SIZE], b[SIZE][SIZE];
constexpr db A = 0.5;
constexpr db B = 1.0 / 3.0;
constexpr db C = 0.25;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int n = 0, st;
struct node {
    int carry; // 是否有种子
    vector<int> graph; // 01图
    int x, y; // 蚂蚁位置
    node() {}
    node(int a, int b, int c, vector<int> g) :carry(a), x(b), y(c), graph(g) {}
    bool operator < (const node& k) const {
        if (carry != k.carry) {
            return carry < k.carry;
        } else if (x != k.x) {
            return x < k.x;
        } else if (y != k.y) {
            return y < k.y;
        } else {
            return graph < k.graph;
        }
    }
};
vector<node> nodes;
map<node, int> mp;

void prepare_nodes() {
    vector<int> s(25, 0);
    for (int i = 20; i < 25; i++) {
        s[i] = 1;
    }
    do { // 蚂蚁不带种子
        int cnt = 0;
        for (int i = 0; i < 5; i++) {
            cnt += s[i];
        }
        if (cnt == 5) continue;
        for (int i = 20; i < 25; i++) {
            cnt += s[i];
        }
        if (cnt == 5) {
            for (int x = 0; x < 5; x++) {
                for (int y = 0; y < 5; y++) {
                    if (x == 4 && s[5 * x + y] == 0) { // 当蚂蚁在第五行时 蚂蚁不能位于有种子的单元格上
                        mp[node(0, x, y, s)] = n++;
                    } else if (x < 4) {
                        mp[node(0, x, y, s)] = n++;
                    }
                }
            }
        }
    } while (next_permutation(s.begin(), s.end()));

    s[20] = 0;
    do { // 蚂蚁带种子
        int cnt = 0;
        for (int i = 0; i < 5; i++) {
            cnt += s[i];
        }
        for (int i = 20; i < 25; i++) {
            cnt += s[i];
        }
        if (cnt == 4) { // 第一行+第五行有四个种子
            for (int x = 1; x < 5; x++) { // 蚂蚁在2/3/4/5行中携带一个种子
                for (int y = 0; y < 5; y++) {
                    mp[node(1, x, y, s)] = n++;
                }
            }
            for (int x = 0; x < 5; x++) { // 蚂蚁在第一行中携带一个种子 当且仅当该单元格已有种子
                if (s[x]) {
                    mp[node(1, 0, x, s)] = n++;
                }
            }
        }
    } while (next_permutation(s.begin(), s.end()));

    s[20] = 1;
    st = mp[node(0, 2, 2, s)];
    reverse(s.begin(), s.end());
    for (int i = 0; i < 5; i++) {
        mp[node(0, 0, i, s)] = n++;
    }
    cout << mp.size() << "\n";
}

inline bool check(int x, int y) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5) return false;
    return true;
}

inline db mapping(int x) {
    if (x == 1) {
        return 1.0;
    } else if (x == 2) {
        return A;
    } else if (x == 3) {
        return B;
    } else {
        return C;
    }
}

void build() {
    nodes.resize(n);
    for (auto i : mp) {
        nodes[i.second] = i.first;
    }
    for (int i = 0; i < n - 5; i++) {
        int x = nodes[i].x, y = nodes[i].y;
        vector<int> go;
        for (int j = 0; j < 4; j++) {
            int tx = x + dx[j];
            int ty = y + dy[j];
            int fork = 5 * tx + ty;
            if (check(tx, ty)) {
                auto nxt = nodes[i];
                if (nodes[i].carry) { // 带有种子
                    if (tx == 0 && nxt.graph[fork] == 0) { // 走到第一行的空位 需要把种子放下
                        nxt.graph[fork] = 1;
                        nxt.carry = 0;
                        nxt.x = tx, nxt.y = ty;
                    } else {
                        nxt.x = tx, nxt.y = ty;
                    }
                } else { // 没有种子
                    if (tx == 4 && nxt.graph[fork] == 1) { // 走到第五行的非空位 需要拿起种子
                        nxt.graph[fork] = 0;
                        nxt.carry = 1;
                        nxt.x = tx, nxt.y = ty;
                    } else {
                        nxt.x = tx, nxt.y = ty;
                    }
                }
                go.push_back(mp[nxt]);
            }
        }
        db prob = mapping((int)go.size());
        for (auto j : go) {
            a[i][j] = prob;
        }
    }
}

void solve() {
    n -= 5;
    cout << n << "\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                b[i][j] = 1;
                a[i][j] = 1.0 - a[i][j];
            } else {
                a[i][j] = -a[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i << "\n";
        db r = a[i][i];
        assert(r != 0);
        for (int j = 0; j < n; j++) {
            a[i][j] /= r;
            b[i][j] /= r;
        }
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            db p = a[j][i];
            for (int k = 0; k < n; k++) {
                a[j][k] -= p * a[i][k];
                b[j][k] -= p * b[i][k];
            }
        }
    }
    db res = 0;
    for (int i = 0; i < n; i++) {
        res += b[st][i];
    }
    cout << fixed << setprecision(20) << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    double t = clock();
    prepare_nodes();
    build();
    solve();
    cout << 1.0 * (clock() - t) / CLOCKS_PER_SEC << "\n";
    return 0;
}