关于此题的前缀和解法

由于本题是需要连续一排的，从而考虑到使用前缀和写法，通过横列和竖列两种状态来存储每一行或每一列的可容纳人数，

之后我们通过找规律,可以发现当该行或该列可容纳n人时，若需要填充k人，则一共有n-(k-1)种情况，对横列进行相加则可以求出答案

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=110;
//前缀和法
char a[N][N];
int col[N][N];//竖列
int row[N][N];//横列
int ans1;
void solve(){
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='.'){
				row[i][j]=row[i][j-1]+1;
			}else{
				row[i][j]=0;
			}
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(a[i][j]=='.'){
				col[i][j]=col[i-1][j]+1;
			}else{
				col[i][j]=0;
			}
		}
	}
	int temp=0,cnt=0;
	//横列
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
      //当一行或一列为0时，证明当前无法容纳，即断开，直接计入
			if(row[i][j]==0){
				cnt+=temp;
				temp=0;
			}
			if(row[i][j]>=k){
				temp=max(temp,row[i][j]-(k-1));
			}
		}
		cnt+=temp;
		ans1+=cnt;
		temp=0,cnt=0;
	}
	temp=0,cnt=0;
	//竖列
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(col[i][j]==0){
				cnt+=temp;
				temp=0;
			}
			if(col[i][j]>=k){
				temp=max(temp,col[i][j]-(k-1));
			}
		}
		cnt+=temp;
		ans1+=cnt;
		temp=0,cnt=0;
	}
	if(k==1){
		cout<<ans1/2;
	}else{
		cout<<ans1;
	}
	return;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}