3 条题解

  • 4
    @ 2026-10-28 8:44:31

    一种较为好写的带权并查集的做法,合并上下、左右相邻的位置,合并时顺便合并两块的方案数。最后对所有极大连通块的方案数求积即可,无需统计每一行的连通块。

    赛时想复杂了。

    #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;
    }
    
    • @ 2026-10-28 9:30:01

      讲的很不错捏

    • @ 2026-10-28 9:40:31

      @ 代码很简单

    • @ 2026-10-28 9:44:47

      lhhsyn,你也写一篇吧。

    • @ 2026-10-28 9:45:33

      @ 还没补完

信息

ID
949
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
36
已通过
12
上传者