你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。
你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。
矩阵树求生成树个数模板题
度数矩阵-邻接矩阵=拉普拉斯矩阵
求拉普拉斯矩阵的任意一个代数余子数即可
#define int long long//记住这个骚操作！！！int->longlong范围懒得手动改。但是记得int main要写成signed main #define mod 1000000000 int tot; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int f[N][N]; char mp[N][N]; int n, m; int id[N][N]; int num = 0; int Gauss() { int ans = 1; for (int i = 1; i < tot; i++) { for (int j = i + 1; j < tot; j++) while (f[j][i]) { int t = f[i][i] / f[j][i]; for (int k = i; k < tot; k++) f[i][k] = (f[i][k] - t * f[j][k] + mod) % mod; swap(f[i], f[j]); ans = -ans; } ans = (ans * f[i][i]) % mod; } return (ans + mod) % mod; } signed main() { sdf(n), sdf(m); for (int i = 1; i <= n; i++) { char c; for (int j = 1; j <= m; j++) { cin >> mp[i][j]; if (mp[i][j] == '.') id[i][j] = ++tot; } } For(x, 1, n) For(y, 1, m) For(k, 0, 3) { int tx = x + dx[k], ty = y + dy[k]; if (tx < 1 || ty < 1 || tx > n || ty > m || mp[x][y] == '*') continue; if (mp[x][y] == mp[tx][ty]) { f[id[x][y]][id[x][y]]++; f[id[x][y]][id[tx][ty]] = -1; f[id[tx][ty]][id[x][y]] = -1; } } printf("%lld ", Gauss()); return 0; }