Cod sursa(job #3264339)

Utilizator Victor5539Tanase Victor Victor5539 Data 20 decembrie 2024 15:49:04
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");


const int ALPHABET=26;
int n,m,fr[ALPHABET+5],i,j,cnt,sp[1005][1005],k;
char v[1005][1005],a;
bool sol[1005][1005];

int nr(char a)
{
    return a-'a'+1;
}

int suma(int x1,int y1,int x2,int y2)
{
    return sp[x2][y2]-sp[x1-1][y2]-sp[x2][y1-1]+sp[x1-1][y1-1];
}

void init()
{
    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>>a;
            fr[nr(a)]++;
        }

    for (i=1; i<=n-m+1; i++)
        for (j=1; j<=n-m+1; j++)
            sol[i][j]=1;
}


void task()
{
    for (k=1; k<=ALPHABET; k++)
    {
        for (i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                sp[i][j]=0;

        for (i=1; i<=n; i++)
            for (j=1; j<=n; j++)
            {
                sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];
                if (k==nr(v[i][j]))
                    sp[i][j]++;
            }

        for (i=1; i<=n-m+1; i++)
            for (j=1; j<=n-m+1; j++)
                if (suma(i,j,i+m-1,j+m-1)!=fr[k])
                    sol[i][j]=0;
    }


    for (i=1; i<=n-m+1; i++)
        for (j=1; j<=n-m+1; j++)
            if (sol[i][j]==1)
                cnt++;

    fout<<cnt;
}

int main()
{
    init();
    task();

    return 0;
}