10pts悬关求助
查看原帖
10pts悬关求助
1181602
Cute_Furina楼主2024/11/9 21:48
#include<bits/stdc++.h>
using namespace std;
char ch[1010][1010];
int n, m, top;
int h[1010], l[1010], r[1010], st[1010];
long long ans;
signed main() {
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			cin >> ch[i][j];
		}
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			h[j] = ch[i][j] == '*'?0 : h[j] + 1;
			
		}
		top = 0;
		for(int j = 1;j <= m;j ++) {
			while(top > 0 && h[i] < h[st[top]]) {
				r[st[top]] = j;
				top --;
			}
			top ++;
			st[top] = j;
		}
		while(top > 0) {
			r[st[top]] = m + 1, top --;
		}
		top = 0;
		for(int j = m;j > 0;j --) {
			while(top > 0 && h[j] <= h[st[top]]) {
				l[st[top]] = j;
				top --;
			}
			top ++, st[top] = j;
		}
		while(top > 0) {
			l[st[top]] = 0;
			top --;
		}
		for(int j = 1;j <= m;j ++) {
			ans += (j - l[j]) * (r[j] - j) * h[j];
		}
	}
	cout << ans;
}
2024/11/9 21:48
加载中...