sixth

_farawaystar_ · 2021-08-26 22:32:53 · 题解

题意简述

求每行每列连续 k 个' . '的情况和。

题目分析

1. 遍历每行：一行中遇到连续 sum 个' . '，则可知，在答案中加上 \max((sum-k+1),0) 个情况。

2. 遍历每列：方法同上。

3. 若 k 为 1 ,则可知：遍历每行每列时，重复计算了两遍，所以只有答案的一半。

代码：

#include<iostream>
#include<cstdio> 
using namespace std;
int n,m,k,ans;
char c[4005][4005];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        getchar();
        int sum=0;
        for(int j=1;j<=m;j++){
            c[i][j]=getchar();
            if(c[i][j]=='.')sum++;
            else{
                ans+=max((sum-k+1),0);
                sum=0;
            }
        }
        ans+=max((sum-k+1),0);
    }
    for(int j=1;j<=m;j++){
        int sum=0;
        for(int i=1;i<=n;i++)
            if(c[i][j]=='.')sum++;
            else{
                ans+=max((sum-k+1),0);
                sum=0;
            }
        ans+=max((sum-k+1),0);
    }
    k==1?cout<<ans/2:cout<<ans;
    return 0;
}

谢谢大家！