Cod sursa(job #3166947)

Utilizator Horia123144Musat Horia Gabriel Horia123144 Data 9 noiembrie 2023 20:01:47
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
char c,a[1005][1005];
int n,m,d[1005][1005],fr[200],sol;
bool ok[1005][1005];

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        fin>>a[i][j];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
    {
        fin>>c;
        fr[c]++;
    }
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
        ok[i][j]=1;
    for(char p='a';p<='z';p++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]==p)
                        d[i][j]=1+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
                else
                    d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
        for(int i=m;i<=n;i++)
            for(int j=m;j<=n;j++)
            if(d[i][j]-d[i-m][j]-d[i][j-m]+d[i-m][j-m]!=fr[p])
                ok[i][j]=0;
        }
        for(int i=m;i<=n;i++)
            for(int j=m;j<=n;j++)
            sol+=ok[i][j];
        fout<<sol;
        return 0;
}