洛谷 3654_First Step (ファーストステップ)_模拟

发布于 2019-05-17  3 次阅读


题目描述

可是……这个篮球场,好像很久没有使用过的样子啊……

里面堆满了学校的各种杂物呢……

我们Aqours的成员要怎么在里面列队站下呢?

我们浦之星女子学院的篮球场是一个R行C列的矩阵,其中堆满了各种学校的杂物 (用”#”表示),空地 (用”.”表示) 好像并不多的样子呢……

我们Aqours现在已经一共有K个队员了,要歌唱舞蹈起来的话,我们得排成一条1*K的直线,一个接一个地站在篮球场的空地上呢 (横竖均可)。

我们想知道一共有多少种可行的站位方式呢。

Aqours的真正的粉丝的你,能帮我们算算吗?


思路

竖着横着枚举判断一下有多少个连着的可以站的地方
随便搞搞就可以了
1的情况要/2


#include 
#include 
#include 
using namespace std;
int a[101][101];
int main()
{
    int n,m,k;
    long long ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
    {
        char ch[1001];
        scanf("%s",ch);
        int t=0;
        for (int j=1;j<=m;j++)
        {
            if (ch[j-1]=='#') a[i][j]=1;
            if (a[i][j]==0) t++;
            if (a[i][j]==1||j==m) 
            {
                if (t>=k) 
                    ans+=t-k+1;
                t=0;
            }
        }
    }
    for (int i=1;i<=m;i++)
    {
        int t=0;
        for (int j=1;j<=n;j++)
        {
            if (a[j][i]==0) t++;
            if (a[j][i]==1||j==n) 
            {
                if (t>=k) 
                    ans+=t-k+1;
                t=0;
            }
        }
    }
    if (k==1) ans/=2;
    printf("%lld",ans);
}
]]>