Cod sursa(job #1773668)

Utilizator Lungu007Lungu Ionut Lungu007 Data 8 octombrie 2016 08:58:30
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#define NMAX 740
#define KMAX 27
using namespace std;

ifstream in("matrix.in");
ofstream out("matrix.out");

int d[NMAX][NMAX][KMAX],a[KMAX],n,m,x,y,contor,sol[KMAX];
char c;
bool ok;

void afmat()
{
       for(int k = 1;k<=4;k++)
   {
        for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
           {
               cout << d[k][i][j] << " ";
           }
           cout << endl;
       }
       cout << endl << endl;
   }
}

void afa()
{
    for(int i=1;i<=5;i++)
    {
        cout << a[i] << " ";
    }
}

int main()
{
    cout << sizeof(d)/1024/1024;

   in >> n >> m;
   in.get();
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           in.get(c);
           //cout << c << " ";
           x = c-'a'+1;
           d[i][j][x] = 1 + d[i-1][j-1][x] + (d[i][j-1][x] - d[i-1][j-1][x]) + (d[i-1][j][x] - d[i-1][j-1][x]);
       }
       in.get();
   }

   for(int i=1;i<=m;i++)
   {
       for(int j=1;j<=m;j++)
       {
           in.get(c);
           x = c-'a'+1;
           a[x]++;
       }
       in.get();
   }


    for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
            for(int k = 1;k<KMAX;k++)
            {
                d[i][j][k] =  d[i][j][k] + d[i-1][j-1][k] + (d[i][j-1][k] - d[i-1][j-1][k]) + (d[i-1][j][k] - d[i-1][j-1][k]);
            }
       }

   }



    for(int i=m;i<=n;i++)
   {
       x = i-m+1;

       for(int j=m;j<=n;j++)
       {
            y = j-m+1;
            for(int z=0;z<KMAX;z++)
            {
                sol[z] = 0;
            }
            for(int k = 1;k<KMAX;k++)
            {
                sol[k] = d[i][j][k] - d[x-1][j][k] - d[i][y-1][k] + d[x-1][y-1][k];
            }
             ok = true;
           for(int z=0;z<KMAX;z++)
           {
               if(sol[z]!=a[z])
               {
                   ok = false;
                   break;
               }
           }

           if(ok)
           {
               contor++;
           }
       }

   }

    out << contor;
   // afmat();
    //afa();
    return 0;
}