FeteSiBaieti

#include <bits/stdc++.h>

using namespace std;
ifstream fin("fetesibaieti.in");
ofstream fout("fetesibaieti.out");
const int di[]= {-1, 0, 1, 0}, dj[]= { 0, 1, 0,-1};
int N, M, K, D;
string s;
int mat[2001][2001], mat2[4001][4001];
void Fill1(int istart,int jstart,int v)
{
    queue<pair<int,int>> Q;
    Q.push(make_pair(istart, jstart));
    mat[istart][jstart] = v;
    while(! Q.empty())
    {
        int i = Q.front().first, j = Q.front().second;
        for(int k = 0 ; k < 4 ; k ++)
        {
            int iv = i + di[k], jv = j + dj[k];
            if(iv>=1 && iv<=K && jv>=1 && jv<=D && mat[iv][jv]==0)
            {
                mat[iv][jv] = v;
                Q.push(make_pair(iv, jv));
            }
        }
        Q.pop();
    }
}
void Fill2(int istart,int jstart,int v, int L, int C)
{
    queue<pair<int,int>> Q1;
    Q1.push(make_pair(istart, jstart));
    mat2[istart][jstart]=v;
    while(!Q1.empty())
    {
        int i=Q1.front().first, j=Q1.front().second;
        for(int k=0 ; k<4; k++)
        {
            int iv=i+di[k], jv=j+dj[k];
            if(iv>=1 && iv<=L && jv>=1 && jv<=C && mat2[iv][jv]==0)
            {
                mat2[iv][jv]=v;
                Q1.push(make_pair(iv, jv));
            }
        }
        Q1.pop();
    }
}
int main()
{
    int i=0, j;
    fin>>K>>N>>D;
    M=N/D;
    fin>>s;
    if(K==D)
    {
        int cnt=0, b=0;
        for(i=0; i<K; ++i)
            if(s[i]=='b')
                b++;
            else
            {
                if(b)
                    cnt++;
                b=0;
            }
        if(b)
            cnt++;
        fout<<cnt;
    }
    else if(N==D && K<D)
    {
        i=0;
        for(int k=1; k<=K; k++)
        {
            for(int d=1; d<=D; d++)
            {
                if(s[i]=='f')
                    mat[k][d]=1;
                i++;
                if(i==K)
                    i=0;
            }
            if(i==K)
                i=0;
        }
        int sol=0;
        for(i=1; i<=K; ++i)
            for(j=1; j<=D; ++j)
                if(!mat[i][j])
                {
                    sol++;
                    Fill1(i,j,sol);
                }
        fout<<sol;
    }
    else
    {
        if(M*K<=4000)
        {
            int second=0, v=2;
            i=0;
            for(int k=1; k<=M*K; k++)
            {
                for(int d=1; d<=D; d++)
                {
                    if(s[i]=='f')
                        mat2[k][d]=1;
                    i++;
                    if(i==K)
                        i=0;
                }
                if(i==K)
                    i=0;
            }
            for(i=1; i<=M*K; ++i)
                for( j=1; j<=D; ++j)
                    if(!mat2[i][j])
                    {
                        second++;
                        Fill2(i,j,v, M*K, D);
                    }
            fout<<second;
        }
        else
        {
            i=0;
            for(int k=1; k<=K; k++)
            {
                for(int d=1; d<=D; d++)
                {
                    if(s[i]=='f')
                        mat[k][d]=1;
                    i++;
                    if(i==K)
                        i=0;
                }
                if(i==K)
                    i=0;
            }
            int p1=0, v=2;
            for(i=1; i<=K; ++i)
                for(j=1; j<=D; ++j)
                    if(!mat[i][j])
                    {
                        p1++;
                        Fill1(i,j,v);
                    }
            int p2=0, v1=2;
            i=0;
            for(int k=1; k<=2*K; k++)
            {
                for(int d=1; d<=D; d++)
                {
                    if(s[i]=='f')
                        mat2[k][d]=1;
                    i++;
                    if(i==K)
                        i=0;
                }
                if(i==K)
                    i=0;
            }
            for(i=1; i<=2*K; ++i)
                for( j=1; j<=D; ++j)
                    if(!mat2[i][j])
                    {
                        p2++;
                        Fill2(i,j,v1, 2*K, D);
                    }
            fout<<M*p1-((M-1)*(2*p1-p2));
        }
    }
    return 0;
}