矩阵树
这题不错，又学到了一个知识点。欸嘿嘿。
题意：
分析：
我们来看这道题：
首先，我们不妨把外面虚拟成一个点。那么问的就是，矩形中的所有点能否到达外面的点。
这时，我们想想。如果能都联通的话应该会是什么情况？
首先肯定有一些点本来就联通。我们以虚构的最外面的点出发，进行深度优先搜索。肯定能将本来就来联通的点标记出来。成为一个连通块1
然后剩下没有搜索到的点有两种情况：
1.他们与'.'联通，构成一个连通块，然后可能可以通过填充'.'来与连通块1联通。
2.他们没有与'.'联通，也就是说这些点无法通过变数'.'来与连通块1联通。over了。
就这两种吧！
那我们不妨把每个连通块都遍历出来好了。
这里再给出一个结论：
每个连通块都至多有一个'.'！这时必然的！
因为对于每一个点入度为1到4但是出度只能为1而'.'的出度为0.也就说明'.'是连通块遍历的终点！！
有点难以理解，不妨画画简单的图，更容易明白。
那么我们，就以最外面的节点和各个'.'为起始节点遍历连通块。
最终遍历出k个连通块。'.'的个数+1
然后看看还有没有没有被遍历到的点。这就是上面的第二种情况。直接over。return 0
都被遍历了后。
我们就要考虑：如何把这些联通块连在一起呢？
依靠填补'.'我们可以和别的连通块连接。那么，一共我们有几种连接方法能使所有的连通块联结在一起呢？
这里就要使用矩阵树定理了！！！！
我们不妨把每一个连通块看组成一个节点。节点i通过'.'能和其他节点建立一些有向边（可能不止一条）。
这样就形成了一张有向图。
我们计算这张图能以1号节点(连通块1)为根能形成多少外向树或者内向树(看你怎么连边了，我是外向树).
这里给一个关于矩阵树的博客，希望对你有所帮助：
https://www.cnblogs.com/ezoiLZH/p/9388855.html
这里再给一个计算行列式的模板：
ll f[max_n][max_n];
ll mod = 1e9 + 7;
ll det(ll n) {
ll res = 1;
for (int i = 1;i <= n;++i) {
if (!f[i][i]) {
bool flag = false;
for (int j = i + 1;j <= n;++j) {
if (f[j][i]) {
flag = true;
for (int k = i;k <= n;++k) swap(f[i][k], f[j][k]);
res = -res;
break;
}
}
if (!flag) return 0;
}
for (int j = i + 1;j <= n;++j) {
while (f[j][i]) {
ll t = f[i][i] / f[j][i];
for (int k = i;k <= n;++k) {
f[i][k] = (f[i][k] - t * f[j][k]) % mod;
swap(f[i][k], f[j][k]);
}
res = -res;
}
}
res *= f[i][i];
res %= mod;
}
if (res < 0) res += mod;
return res;
}如此，答案就出来了。
代码如下：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int max_n = 210;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
char G[max_n][max_n];
int col[max_n][max_n];
int cnt = 1;
int tot = 0;
vector<pii> point;
const ll mod = 1e9 + 7;
ll f[410][410];
ll det(ll n) {
ll res = 1;
for (int i = 2;i <= n;++i) {
if (!f[i][i]) {
bool flag = false;
for (int j = i + 1;j <= n;++j) {
if (f[j][i]) {
flag = true;
for (int k = i;k <= n;++k) swap(f[i][k], f[j][k]);
res = -res;
break;
}
}
if (!flag) return 0;
}
for (int j = i + 1;j <= n;++j) {
while (f[j][i]) {
ll t = f[i][i] / f[j][i];
for (int k = i;k <= n;++k) {
f[i][k] = (f[i][k] - t * f[j][k]) % mod;
swap(f[i][k], f[j][k]);
}
res = -res;
}
}
res *= f[i][i];
res %= mod;
}
if (res < 0) res += mod;
return res;
}
void dfs(int sx,int sy,int color) {
tot++;
col[sx][sy] = color;
if (sx - 1 > 0 && G[sx - 1][sy] == 'D')dfs(sx - 1, sy, color);
if (sx + 1 <= n && G[sx + 1][sy] == 'U')dfs(sx + 1, sy, color);
if (sy - 1 > 0 && G[sx][sy - 1] == 'R')dfs(sx, sy - 1, color);
if (sy + 1 <= m && G[sx][sy + 1] == 'L')dfs(sx, sy + 1, color);
}
void init() {
point.clear();
for (int i = 0;i <= 310;i++)
for (int j = 0;j <= 310;j++)
f[i][j] = 0;
for (int i = 0;i <= n;i++)
for (int j = 0;j <= m;j++)
col[i][j] = 0;
cnt = 1;tot = 0;
}
int main() {
ios::sync_with_stdio(0);
int t;cin >> t;
while (t--) {
cin >> n >> m;init();
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++) {
cin >> G[i][j];
if (G[i][j] == '.')
point.push_back({ i,j });
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
if (G[i][j] == '.')
dfs(i, j, ++cnt);
else if (i == 1 && G[i][j] == 'U' || j == 1 && G[i][j] == 'L' || i == n && G[i][j] == 'D' || j == m && G[i][j] == 'R')
dfs(i, j, 1);
}
}
if (tot != n * m) {
cout << 0 << endl;
continue;
}
for (int i = 0;i < point.size();i++) {
pii p = point[i];
int x = p.first;int y = p.second;
int val = col[x][y];
if (x == 1) {
f[1][val]--;
f[val][val]++;
}
if (x == n) {
f[1][val]--;
f[val][val]++;
}
if (y == 1) {
f[val][val]++;
f[1][val]--;
}
if (y == m) {
f[val][val]++;
f[1][val]--;
}
if (x != 1) {
int to = col[x - 1][y];
if (to != val) {
f[to][val]--;
f[val][val]++;
}
}
if (x != n) {
int to = col[x + 1][y];
if (to != val) {
f[to][val]--;
f[val][val]++;
}
}
if (y != m) {
int to = col[x][y + 1];
if (to != val) {
f[to][val]--;
f[val][val]++;
}
}
if (y != 1) {
int to = col[x][y - 1];
if (to != val) {
f[to][val]--;
f[val][val]++;
}
}
}
cout << det(cnt) << endl;
}
}//话说为什么会有最小生成树的标签啊？！
京公网安备 11010502036488号