题目大意：给定一张边框确定的图，在其中空地放水并满足物理要求，求总方案数
题目分析： 首先注意到，满足物理需求就是满足在一个连通块内从高度为 \(h\) 放水，则满足对于高度为 \(\forall\) \(i\) \(\le\) \(h\)的空地均有水。
那么显而易见，我们可以从下到上枚举高度，对于连通性用并查集来维护一下就可以了。
至于连通性我们可以想到改连通块打上编号
int get_id(int x , int y) {
return m * (x - 1) + y;
}
我们定义 \(f (i)\) 为编号为 \(i\) 的联通块填水的方案数
对于两个连通块 \(i , j\) 的合并分为两种情况 ：
- [\(1\)] : 若 \(i , j\) 同行， 则直接合并就可以
- [\(2\)] : 若 \(i , j\) 不同行 ， 设 \(h_i = h_j + 1\) 则 \(f_i = f_i * f_j\) 。
- [\(3\)] : 对于情况 \(1, 2\) , 合并之后所形成的新的连通块也是一种情况，所以在合并之后需要将新的连通块 \(k\) 的方案数 \(f_k + 1\).
对于最后的 \(Ans\) 即为 \(\begin{matrix} \prod_{i=1}^{n * m} f_i \end{matrix}\)
``
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int M = 4e6 + 7;
int fa[M] , f[M];
int a[1007][1007];
int n , m;
int getfa(int x) {
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
int g(int x , int y) {
return m * (x - 1) + y;
}
signed main () {
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) {
char c;
for(int j = 1; j <= m; ++ j) {
cin >> c;
if(c == '.') a[i][j] = 1;
}
}
for(int i = n * m; i >= 1; -- i) fa[i] = i , f[i] = 1;
for(int i = n - 1; i > 1; -- i) {
for(int j = 2; j < m; ++ j) if(a[i][j] && a[i][j + 1]) fa[getfa(g(i , j))] = getfa(g(i , j + 1));
for(int j = 2; j < m; ++ j) if(a[i][j] && a[i + 1][j]) if(getfa(g(i , j)) != getfa(g(i + 1 , j))) f[getfa(g(i , j))] = f[getfa(g(i + 1 , j))] * f[getfa(g(i , j))] % mod , fa[getfa(g(i + 1, j))] = getfa(g(i , j));
for(int j = 2; j < m; ++ j) if(a[i][j] && getfa(g(i , j)) == g(i , j)) f[g(i , j)] ++;
}
int ans = 1;
for(int i = 2; i <= n - 1; ++ i) for(int j = 2; j < m; ++ j) if(a[i][j] &&getfa(g(i , j)) == g(i , j)) ans = ans * f[g(i , j)] % mod;
cout << ans;
return 0;
}
本题完结
标签：连通,return,fa,int,++,计数,简单,getfa,P6008 From： https://www.cnblogs.com/Love-yx/p/16655093.html