Cod sursa(job #3167505)

Utilizator Cazacu2006RazvanRazvan Cazacu Cazacu2006Razvan Data 10 noiembrie 2023 19:25:41
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int n,m,a[1001][1001],fr[30],ok[1001][1001],s[1001][1001],sol;
char x[1001];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        for(int j=0;j<n;j++)
        {
            a[i][j+1]=x[j]-'a'+1;
            ok[i][j+1]=1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x;
        for(int j=0;j<m;j++)
        {
            fr[x[j]-'a'+1]++;
        }
    }

    for(int p=1;p<=26;p++)
    {


        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]!=p)
                s[i][j]=0;
               else
                s[i][j]=1;

              s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];



            }

        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {

                int suma=s[i][j]-s[max(0,i-m)][j]-s[i][max(j-m,0)]+s[max(i-m,0)][max(0,j-m)];

                if(suma!=fr[p])
                {
                    ok[i][j]=0;
                }
            }
        }

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {

            sol+=ok[i][j];
        }
    }
    fout<<sol;

    return 0;
}