本文共 2124 字，大约阅读时间需要 7 分钟。

题意：n*m的字符矩阵，'.'代表卧室，'*'代表厨房。卧室与卧室之间有一扇门，要求任意两个卧室之间只有一条路。求路的总数。

题解：生成树计数模板题

无向图的基尔霍夫矩阵: 对角线上表示每个点的度数，若ij之间有边则矩阵ij处为-1。其他ij的值为0。

无向图的生成树的数目为: 任意一个n-1阶主子式的行列式的绝对值。（下面是模板）

1.模板题，这个可以转化为生成树计数，遇到求无向图的生成树个数，直接套用这个模板就ok。

#include 
   
    #include
    
     #include
     
      #define MOD 1000000000using namespace std;int cnt = 0 ;int index[15][15] ;int row[4] = {0 , 0 , -1 , 1} ;int col[4] = {-1 , 1 , 0 , 0} ;bool A[105][105] ;long long B[105][105] ;long long det(int n) //计算n-1阶行列式 {   int i , j , k ;  long long t , ans = 1 ;   for(i = 0 ; i < n ; i ++)   {       for(j = i + 1 ; j < n ; j ++)       {         while(B[j][i])         {           t = B[i][i] / B[j][i];           for(k = i ; k < n ; k ++)           {              B[i][k] = (B[i][k] - B[j][k] * t % MOD + MOD) % MOD ;              swap(B[i][k] , B[j][k]) ;           }           ans = -ans ;         }       }       if(!B[i][i])           return 0;       ans = ans * B[i][i] % MOD ;   }   return (ans + MOD) % MOD ; } int main(){	int i , j , k ;    int n , m ;    int begin , end ;    long long ans ;    int x , y ;    char map1[15][15] ;    scanf("%d%d", &n, &m) ; 	memset(index , -1 , sizeof(index)); 	memset(A , 0 , sizeof(A));    memset(B , 0 , sizeof(B));    for(i = 0 ; i < n ; i ++)        scanf("%s" , map1[i]) ;    for(i = 0 ; i < n ; i ++)	    for(j = 0 ; j < m ; j ++)		    if(map1[i][j] == '.')			   index[i][j] = cnt ++ ;     for(i = 0 ; i < n ; i ++)        for(j = 0 ; j < m ; j ++)        {        	if(map1[i][j] == '*')        	   continue ;        	for(k = 0 ; k < 4 ; k ++)            {               x = i + row[k] ;               y = j + col[k] ;               if(x < 0 || x >= n || y < 0 || y >= m)                  continue ;               if(map1[x][y] == '*')                  continue ;               begin = index[i][j] ;               end = index[x][y] ;               A[begin][end] = 1 ;			}		}    for(i = 0 ; i < cnt ; i ++)        for(j = 0 ; j < cnt ; j ++)            if(i != j && A[i][j])			{                B[i][i] ++ ;                B[i][j] = -1 ;             }    ans = det(cnt - 1) ;     printf("%lld\n", ans);    return 0;}