Join
题目链接：https://vjudge.net/problem/URAL-1627
Description:
Businessman Petya recently bought a new house. This house has one floor with n × m square rooms, placed in rectangular lattice. Some rooms are pantries and the other ones are bedrooms. Now he wants to join all bedrooms with doors in such a way that there will be exactly one way between any pair of them. He can make doors only between neighbouring bedrooms (i.e. bedrooms having a common wall). Now he wants to count the number of different ways he can do it.
Input:
First line contains two integers n and m (1 ≤ n, m ≤ 9) — the number of lines and columns in the lattice. Next n lines contain exactly m characters representing house map, where "." means bedroom and "*" means pantry. It is guaranteed that there is at least one bedroom in the house.
Output:
Output the number of ways to join bedrooms modulo 10 .
Sample Input:
2 2
.*
*.
Sample Output:
0
题意：
给出一个n*m的矩阵，然后"*"表示障碍物。现在可以在两个"."之间搭桥，问有多少种方式将所有的"."连通。
题解：
直接给所有能够搭桥的点建边，然后就是个生成树计数问题了。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = ,MOD = 1e9;
char mp[N][N];
int g[N][N],num[N][N];
ll b[N][N];
int tot=;
ll Det(int n){
int i,j,k;
ll ret = ;
if(n==) return ;
for(i=;i<=n;i++){
for(j = i+;j <= n;j++){
while(b[j][i]){
ll tmp=b[i][i]/b[j][i];//不存在除不尽的情况
for(k = i;k <= n;k++)
b[i][k] = ((b[i][k] - tmp*b[j][k])%MOD+MOD)%MOD;
for(k=i;k<=n;k++)
swap(b[i][k],b[j][k]);
ret = -ret;
}
}
if(!b[i][i]) return ;
ret = ret * b[i][i]%MOD;
if(ret<) ret+=MOD;
}
if(ret < ) ret += MOD;
return ret;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",mp[i]+);
for(int j=;j<=m;j++){
if(mp[i][j]=='.') num[i][j]=++tot;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='*') continue ;
if(j>&&mp[i][j-]=='.') g[num[i][j-]][num[i][j]]=;
if(i<n&&mp[i+][j]=='.') g[num[i+][j]][num[i][j]]=;
}
}
for(int i=;i<=tot;i++){
for(int j=;j<=tot;j++){
if(g[i][j]){
b[i][i]++;b[j][j]++;
b[i][j]=b[j][i]=-;
}
}
}
cout<<Det(tot);
return ;
}