30tps,求助!
查看原帖
30tps,求助!
907430
corner_xiejunqi楼主2024/11/30 12:17
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10; 
int n,m;
char g[N][N],h[N][N],l[N],r[N];
inline void calc(int x){
	stack<int> st,st1;
	for(int i=1;i<=m;i++){
		while(!st.empty() && h[x][i]<h[x][st.top()]){r[st.top()]=i;st.pop();}
		st.push(i);
	}
	while(!st.empty()){r[st.top()]=m+1;st.pop();}
	for(int i=m;i>=1;i--){
		while(!st1.empty() && h[x][i]<=h[x][st1.top()]){l[st1.top()]=i,st1.pop();}
		st1.push(i);
	}
	while(!st1.empty()){l[st1.top()]=0,st1.pop();}
}
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='.') h[i][j]=h[i-1][j]+1;
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		calc(i);
		for(int j=1;j<=m;j++) tot+=(j-l[j])*(r[j]-j)*h[i][j];
	}
	cout<<tot;
	return 0;
}
2024/11/30 12:17
加载中...