圆方树

首先大力 sto $\mathrm{\color{black}{Y}\color{red}{CS\_GG}}$ orz，你这道题就完成一半了。

人可以随意走动，而箱子只能随人动。我们考虑找出所有人和箱子相邻时的位置情况，对于确定的箱子的位置，只要统计人能够到达的位置数量。

我们要处理 $f(x,y,d)$ 表示箱子在 $(x,y)$ 位置，人在箱子 $d$ 方向相邻位置的情况是否能够到达终点。可以逆向考虑，从终点开始 bfs，那么有两种转移的可能：

$$f(x,y,d)\to\begin{cases} f(x',y',d)&\text{沿着 $d$ 方向向前走一步}\\ f(x,y,k)&\text{人相对于箱子的方向变为 $k$} \end{cases} $$

由于题目要求，人移动不能经过箱子，所以改变方向的转移需要判断的是：$d$ 方向相邻的格子 $(x',y')$ 和 $k$ 方向相邻的格子 $(x'',y'')$ 之间是否存在超过两条不相交路径，或者说是否属于同一个点双连通分量。

那么对终点所在的连通图建出圆方树，只要判断两点间距离是否等于 $2$ 即可。

现在对于所有可能的箱子和人相邻时的位置情况 $((x,y),(x',y'))$，设其树上编号分别为 $u,v$，统计 $v$ 不经过 $u$ 能够到达的位置数量。

在圆方树上，删去 $u$ 后会形成若干个连通块，包含 $v$ 的连通块大小就是 $v$ 不经过 $u$ 能够到达的位置数量。注意需要去重，并且人不能与终点重合。

复杂度 $\mathcal O(nm)$，常数感人，并且会被卡空间常数，构建圆方树时把原图清空可以卡过。

#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using i64 = long long;

int dx[] = { 0, 1, -1, 0 };
int dy[] = { 1, 0, 0, -1 };

int n, m;
int g_tot;
std::vector<std::string> map;
std::vector<std::vector<int>> id;
std::vector<std::vector<int>> e;

bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m;
}

void pre_dfs(int i, int j) {
    id[i][j] = g_tot++;
    for (int k = 0; k < 4; ++k) {
        int x = i + dx[k], y = j + dy[k];
        if (inside(x, y) && map[x][y] != '#' && id[x][y] == -1)
            pre_dfs(x, y);
    }
}

int dfc, tr_tot;
std::vector<int> dfn, low, stk;
std::vector<std::pair<int, int>> tmp;

void Tarjan(int u) {
    dfn[u] = low[u] = dfc++;
    stk.push_back(u);
    for (auto v : e[u]) {
        if (dfn[v] == -1) {
            Tarjan(v);
            low[u] = std::min(low[u], low[v]);
            if (low[v] == dfn[u]) {
                int x;
                do {
                    x = stk.back();
                    stk.pop_back();
                    tmp.emplace_back(tr_tot, x);
                } while (x != v);
                tmp.emplace_back(tr_tot, u);
                tr_tot++;
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}

std::vector<int> dep, size, fa;

void tr_dfs(int u, int fat) {
    if (~fat) dep[u] = dep[fat] + 1;
    fa[u] = fat;
    size[u] = u < g_tot;
    for (auto v : e[u]) {
        if (v == fat) continue;
        tr_dfs(v, u);
        size[u] += size[v];
    }
}

std::vector<std::vector<std::vector<bool>>> can;

bool reach(int x, int y) {
    if (fa[x] == fa[y]) return true;
    if (~fa[x] && fa[fa[x]] == y) return true;
    if (~fa[y] && fa[fa[y]] == x) return true;
    return false;
}

void bfs(int sx, int sy) {
    can.resize(n, std::vector<std::vector<bool>>(m, std::vector<bool>(4, false)));
    struct Point { int x, y, d; };
    std::queue<Point> que;
    for (int k = 0; k < 4; ++k) {
        int x = sx + dx[k], y = sy + dy[k];
        if (inside(x, y) && ~id[x][y]) {
            can[sx][sy][k] = true;
            que.push({sx, sy, k});
        }
    }
    while (!que.empty()) {
        auto p = que.front();
        que.pop();
        int i = p.x, j = p.y, d = p.d;
        // go straignt
        int x = i + dx[d], y = j + dy[d];
        int xx = x + dx[d], yy = y + dy[d];
        if (inside(xx, yy) && ~id[xx][yy] && !can[x][y][d]) {
            can[x][y][d] = true;
            que.push({x, y, d});
        }
        // turn around
        for (int k = 0; k < 4; ++k) {
            if (can[i][j][k]) continue;
            int tx = i + dx[k], ty = j + dy[k];
            if (inside(tx, ty) && ~id[tx][ty] && reach(id[x][y], id[tx][ty])) {
                can[i][j][k] = true;
                que.push({i, j, k});
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m;
    map.resize(n);
    int sx = -1, sy = -1;
    for (int i = 0; i < n; ++i) {
        std::cin >> map[i];
        for (int j = 0; j < m; ++j)
            if (map[i][j] == 'X')
                sx = i, sy = j;
    }
    id.resize(n, std::vector<int>(m, -1));
    pre_dfs(sx, sy);
    e.resize(g_tot);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (id[i][j] == -1) continue;
            for (int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                if (inside(x, y) && ~id[x][y])
                    e[id[i][j]].push_back(id[x][y]);
            }
        }
    }

    tr_tot = g_tot;
    dfn.resize(g_tot, -1);
    low.resize(g_tot, -1);
    Tarjan(id[sx][sy]);
    e.assign(tr_tot, std::vector<int>());
    for (auto i : tmp) {
        e[i.first].push_back(i.second);
        e[i.second].push_back(i.first);
    }
    dep.resize(tr_tot);
    size.resize(tr_tot);
    fa.resize(tr_tot);
    tr_dfs(id[sx][sy], -1);

    bfs(sx, sy);

    i64 ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (id[i][j] == -1 || (i == sx && j == sy)) continue;
            bool vis = false;
            std::vector<int> alr;
            for (int k = 0; k < 4; ++k) {
                if (!can[i][j][k]) continue;
                int x = i + dx[k], y = j + dy[k];
                if (!inside(x, y) || id[x][y] == -1) continue;
                int u = id[i][j], v = id[x][y];
                if (!reach(u, v)) continue;
                if (~fa[v] && fa[fa[v]] == u) {
                    if (std::find(alr.begin(), alr.end(), fa[v]) == alr.end()) {
                        ans += size[fa[v]];
                        alr.push_back(fa[v]);
                    }
                }
                else {
                    if (!vis) {
                        ans += g_tot - size[u] - 1;
                        vis = true;
                    }
                }
            }
        }
    }
    std::cout << ans << '\n';

    return 0;
}