3 条题解
-
4
一种较为好写的带权并查集的做法,合并上下、左右相邻的位置,合并时顺便合并两块的方案数。最后对所有极大连通块的方案数求积即可,无需统计每一行的连通块。
赛时想复杂了。
#include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int N = 1e3 + 5, V = 1e6 + 5; ll n, m, ans; ll f(int x, int y) { return (x - 1) * m + y; } char s[N][N]; int fa[V], vis[V], val[V]; void init() { for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { int cur = f(i, j); fa[cur] = cur; val[cur] = 1; } } } int get(int u) { if(fa[u] == u) return u; return fa[u] = get(fa[u]); } void merge(int u, int v) { int fu = get(u), fv = get(v); if(fu != fv) { fa[fv] = fu; val[fu] *= val[fv], val[fu] %= MOD; } } signed main() { ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { cin >> s[i][j]; } } init(); for(int i=n-1; i>=2; --i) { for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(s[i][j - 1] == s[i][j]) merge(f(i, j - 1), f(i, j)); } for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(s[i + 1][j] == s[i][j]) merge(f(i, j), f(i + 1, j)); } for(int j=2; j<m; ++j) { int fn = get(f(i, j)); if(vis[fn]) continue; vis[fn] = 1, ++val[fn]; } } ans = 1; for(int i=n-1; i>=2; --i) { for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(fa[f(i, j)] == f(i, j)) ans *= val[f(i, j)], ans %= MOD; } } cout << ans << '\n'; return 0; }
信息
- ID
- 949
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 36
- 已通过
- 12
- 上传者