洛谷4111 [HEOI2015]小Z的房间

• 不要直接把各格子编号作为点编号，那样不连通。
• 基尔霍夫矩阵是度数矩阵减邻接矩阵
• 每次交换行列结果取反。

// luogu-judger-enable-o2
#include <iostream>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9;
const int_t LARGE = 100;
int_t mat[LARGE + 1][LARGE + 1];
char mat0[LARGE + 1][LARGE + 1];
int_t map[LARGE + 1][LARGE + 1];
int_t used = 0;
int_t n, m;
void pushEdge(int_t from, int_t to) {
    if (from < to) {
        mat[from][to] = mat[to][from] = -1;
        mat[from][from]++;
        mat[to][to]++;
#ifdef DEBUG
        cout << "edge " << from << "," << to << endl;
#endif
    }
}
int_t encode(int_t r, int_t c) { return (r - 1) * m + c; }
int main() {
    cin >> n >> m;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j <= m; j++) {
            char& chr = mat0[i][j];
            cin >> chr;
            if (chr == '.') map[i][j] = ++used;
        }
    }
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = 1; j <= m; j++) {
            char& chr = mat0[i][j];
            if (chr == '*') continue;
            const auto check = [&](int_t rx, int_t cx) {
                if (rx >= 1 && rx <= n && cx >= 1 && cx <= m) {
                    if (mat0[rx][cx] != '*') {
                        pushEdge(map[i][j], map[rx][cx]);
                    }
                }
            };
            check(i + 1, j);
            check(i - 1, j);
            check(i, j + 1);
            check(i, j - 1);
        }
    }
    int_t len = used - 1;
    int_t flag = 1;
    for (int_t i = 1; i <= len; i++) {
#ifdef DEBUG
        cout << "main at " << i << endl;
#endif
        int_t next = i;
        for (int_t j = i + 1; j <= len; j++) {
            if (std::abs(mat[j][i]) > std::abs(mat[i][i])) {
                next = j;
            }
        }
        if (next != i) {
            flag *= -1;
#ifdef DEBUG
            cout << "to " << flag << " when swap " << next << "," << i << endl;
#endif
            std::swap(mat[i], mat[next]);
        }
        for (int_t j = i + 1; j <= len; j++) {
#ifdef DEBUG
            cout << "line " << j << endl;
#endif
            while (mat[j][i]) {
                int_t t = mat[j][i] / mat[i][i];
#ifdef DEBUG
                cout << t << endl;
#endif
                for (int_t k = i; k <= len; k++)
                    mat[j][k] =
                        (mat[j][k] - t * mat[i][k] % mod + 2 * mod) % mod;
                if (mat[j][i] == 0) break;
                std::swap(mat[j], mat[i]);
                flag *= -1;
#ifdef DEBUG
                cout << "-> to " << flag << " when " << j << "," << i << endl;
#endif
            }
        }
    }
    int_t result = 1;
#ifdef DEBUG
    cout << "flag" << flag << endl;
#endif
    for (int_t i = 1; i <= len; i++) {
        result = result * (mod + mat[i][i]) % mod;
#ifdef DEBUG
        cout << mat[i][i] << endl;
#endif
    }
    cout << (result * flag + mod) % mod << endl;
    return 0;
}