Cod sursa(job #3329418)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 13 decembrie 2025 10:21:46
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
const int lim=1e3+5;
int n,m,i,j,f[lim][lim],frecva,frecvc,cnt,k,ideal[lim][lim],ok;
char t,v[lim][lim],p[lim][lim];
bool sol[lim][lim][27];
set< int> car;
int main()
{
    fin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            fin>>v[i][j];
    for(i=1; i<=m; i++)
        for(j=1; j<=m; j++)
            fin>>p[i][j];

    for(k=0; k<=25; k++)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            f[i][j]=ideal[i][j]=0;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
                if(v[i][j]-'a'==25)f[i][j]++;
            }
        for(i=1; i<=m; i++)
            for(j=1; j<=m; j++)
            {
                ideal[i][j]=ideal[i-1][j]+ideal[i][j-1]-ideal[i-1][j-1];
                if(p[i][j]-'a'==25)ideal[i][j]++;
            }
        for(i=m; i<=n; i++)
            for(j=m; j<=n; j++)
            {
                ok=1;
                frecva=f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m];
                frecvc=ideal[m][m];
                if(frecva<frecvc)
                {
                    ok=0;
                    break;
                }
                if(ok==1)sol[i][j][k]=1;
            }

    }
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
        car.insert(p[i][j]-'a');
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            ok=1;
            for(auto x:car)
    {
        if(sol[i][j][x]==0)ok=0;
    }
    if(ok==1)cnt++;
        }
    fout<<cnt;
    return 0;
}