Cod sursa(job #3255344)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 10 noiembrie 2024 13:34:49
Problema Matrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int nmax = 1000;


int n,m;

int txt[nmax+5][nmax+5];

int pat[nmax +5][nmax + 5];

char pch[nmax + 5][nmax + 5];
char txh[nmax + 5][nmax + 5];

int p;

int sol;

int f[35];
int f2[35];


void check(int x,int y)
{

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[pch[i][j]-'a']++,f2[txh[i+x-1][j+y-1]-'a']++;
    bool ok = true;
    for(int i='a';i<='z';i++)
    {
        if(f[i-'a']!=f2[i-'a'])
            ok=false;
        f[i-'a']=f2[i-'a'];
    }
    if(ok)
        sol++;
}

int main()
{
    fin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char x;
            fin>>x;
            txh[i][j]=x;
            txt[i][j] = (1<<(x-'a'));
            txt[i][j]+=txt[i-1][j]+txt[i][j-1]-txt[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char x;
            fin>>x;
            pch[i][j]=x;
            pat[i][j]=(1<<(x-'a'));
            p+=pat[i][j];
        }
    }

    for(int i=1;i+n-1<=m;i++)
    {
        for(int j=1;j+n-1<=m;j++)
        {
            int sum = txt[i+n-1][j+n-1] + txt[i-1][j-1] - txt[i+n-1][j-1] - txt[i-1][j+n-1];
            if(sum==p)
                check(i,j);

        }
    }
    fout<<sol;
}