Cod sursa(job #3167931)

Utilizator gabriel.9619Gabriel Stefan Tita gabriel.9619 Data 11 noiembrie 2023 12:03:14
Problema Matrix Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");

char a[1005][1005];
int dp[1005][1005], ok[1005][1005], f[150];

int main()
{
    char x;
    int n, m, i, j, c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            fin>>a[i][j];
        }
    }
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=m;j++)
        {
            fin>>x;
            f[x]++;
        }
    }

    for(i=m;i<=n;i++)
    {
        for(j=m;j<=n;j++)
        {
            ok[i][j]=1;
        }
    }

    for(c='a';c<='z';c++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(a[i][j]==c)
                {
                    dp[i][j]=1+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
                }
                else
                {
                    dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
                }
            }
        }
        for(i=m;i<=n;i++)
        {
            for(j=m;j<=n;j++)
            {
                if(dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]!=f[c])
                {
                    ok[i][j]=0;
                }
            }
        }
    }
    int sol=0;
    for(i=m;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(ok[i][j]==1)
            {
                sol++;
            }
        }
    }
    fout<<sol;
}