题解

思路

把同色且四联通的棋子看成连通块。一个白棋连通块存活，当且仅当其中至少一个棋子与空点相邻。先求原棋盘中所有白棋块的大小、气源数量以及未存活白棋总数 $base$。

翻转黑棋时，它变成白棋并合并至相邻的若干白棋块。若新棋子邻接空点，或相邻白棋块中至少一个原本存活，合并后的大块存活；此时从 $base$ 中扣除所有相邻死白块的大小。否则合并块仍死亡，只需在 $base$ 上加上新白棋这一枚。

翻转白棋时，相当于从它所在的白棋图中删除该顶点。只有该连通块可能改变。对每个白棋块做 DFS，记录 $dfn,low$、DFS 子树大小以及子树中的气源数。删除顶点 $u$ 后，每个满足 $low_v\ge dfn_u$ 的 DFS 儿子子树会独立分离；若该子树没有气源，其中全部白棋死亡。其余顶点组成至多一个剩余部分，同样按气源数判断是否死亡。原本死亡的整块先从 $base$ 中扣除，再加入删除后各死亡部分的大小。

棋盘可能有 $10^6$ 个点，DFS 使用显式栈实现，避免递归栈溢出。

做法

1. 标记每枚白棋是否邻接空点。
2. 对白棋图执行迭代 Tarjan DFS，求连通块编号、块大小、气源数、$dfn,low$、子树大小和子树气源数。
3. 汇总原棋盘的未存活白棋数 $base$。
4. 对每个白棋顶点，根据割点分离子树与剩余部分计算翻转答案。
5. 对每个黑棋顶点，去重相邻白棋块并判断合并块是否存活。
6. 按行列顺序将各棋子的答案以底数 $10^6+7$ 编码。

证明

白棋块是否存活只由块内是否存在邻接空点的棋子决定。翻转黑棋不会创造或删除空点，只会把相邻白棋块与新白棋合并，因此合并块存活的充要条件正是新棋子邻接空点或至少一个被合并白块存活；相应的死亡白棋增减与算法一致。

翻转白棋不会影响其他白棋块。无向图删除 $u$ 后，DFS 儿子 $v$ 的子树在 $low_v\ge dfn_u$ 时与其余部分断开，所有不满足条件的子树仍与祖先侧连通；因此算法列出的分离子树和一个剩余部分恰好是删除后的全部连通块。每个部分的子树气源计数等于其中邻接空点的棋子数，所以算法对其生死判断正确。两类翻转覆盖所有棋子，最后编码顺序与题意相同，故答案正确。

复杂度

• 时间复杂度：每组测试数据 $O(n^2)$。
• 空间复杂度：$O(n^2)$。

参考实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007, BASE = 1000007;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<string> g(n);
        for (auto &s : g) cin >> s;
        int N = n * n, tim = 0;
        vector<int> dfn(N), low(N), par(N, -1), it(N), sub(N), src(N), comp(N, -1);
        vector<char> liberty(N, 0);
        auto inside = [&](int r, int c) { return r >= 0 && r < n && c >= 0 && c < n; };
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) if (g[r][c] == 'o') {
            int u = r * n + c;
            for (int k = 0; k < 4; k++) {
                int x = r + dr[k], y = c + dc[k];
                if (inside(x, y) && g[x][y] == '.') liberty[u] = 1;
            }
        }
        vector<int> csz, csrc;
        for (int s = 0; s < N; s++) if (g[s / n][s % n] == 'o' && !dfn[s]) {
            int cid = (int)csz.size();
            vector<int> st(1, s);
            dfn[s] = low[s] = ++tim;
            sub[s] = 1; src[s] = liberty[s]; comp[s] = cid;
            while (!st.empty()) {
                int u = st.back();
                if (it[u] < 4) {
                    int k = it[u]++, r = u / n + dr[k], c = u % n + dc[k];
                    if (!inside(r, c) || g[r][c] != 'o') continue;
                    int v = r * n + c;
                    if (!dfn[v]) {
                        par[v] = u; comp[v] = cid; dfn[v] = low[v] = ++tim;
                        sub[v] = 1; src[v] = liberty[v]; st.push_back(v);
                    } else if (v != par[u]) low[u] = min(low[u], dfn[v]);
                } else {
                    st.pop_back();
                    if (par[u] != -1) {
                        low[par[u]] = min(low[par[u]], low[u]);
                        sub[par[u]] += sub[u]; src[par[u]] += src[u];
                    }
                }
            }
            csz.push_back(sub[s]); csrc.push_back(src[s]);
        }
        ll base = 0;
        for (int i = 0; i < (int)csz.size(); i++) if (!csrc[i]) base += csz[i];
        vector<ll> val(N, 0);
        for (int u = 0; u < N; u++) if (g[u / n][u % n] == 'o') {
            int cutSize = 0, cutSrc = 0;
            for (int k = 0; k < 4; k++) {
                int r = u / n + dr[k], c = u % n + dc[k];
                if (!inside(r, c)) continue;
                int v = r * n + c;
                if (par[v] == u && low[v] >= dfn[u]) {
                    if (src[v] == 0) val[u] += sub[v];
                    cutSize += sub[v]; cutSrc += src[v];
                }
            }
            int id = comp[u];
            val[u] += base - (csrc[id] == 0 ? csz[id] : 0);
            int restSize = csz[id] - 1 - cutSize;
            int restSrc = csrc[id] - liberty[u] - cutSrc;
            if (restSize > 0 && restSrc == 0) val[u] += restSize;
        }
        for (int u = 0; u < N; u++) if (g[u / n][u % n] == 'x') {
            bool alive = false;
            int ids[4], cnt = 0;
            ll removed = 0;
            for (int k = 0; k < 4; k++) {
                int r = u / n + dr[k], c = u % n + dc[k];
                if (!inside(r, c)) continue;
                if (g[r][c] == '.') alive = true;
                if (g[r][c] != 'o') continue;
                int id = comp[r * n + c];
                bool seen = false;
                for (int j = 0; j < cnt; j++) seen |= ids[j] == id;
                if (seen) continue;
                ids[cnt++] = id;
                if (csrc[id]) alive = true;
                else removed += csz[id];
            }
            val[u] = alive ? base - removed : base + 1;
        }
        ll ans = 0;
        for (int u = 0; u < N; u++) if (g[u / n][u % n] != '.') ans = (ans * BASE + val[u]) % MOD;
        cout << ans << '\n';
    }
    return 0;
}