Cod sursa(job #1011192)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 16 octombrie 2013 15:28:00
Problema Matrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
int n,m,a[1005][1005],def[30],v1[30],v2[30],sol=0;
void Read()
{ int i,j; char sir[2005];
   f>>n>>m;
  for(i=1;i<=n;i++)
  { f>>sir;
    for(j=0;j<n;j++)
     a[i][j+1]=sir[j]-97;
  }
  for(i=1;i<=m;i++)
  { f>>sir;
    for(j=0;j<m;j++)
     def[sir[j]-97]++;
  }
}

void Solve()
{ int i,j,t,l,c,bad,badinit;
  for(i=1;i<=m;i++)
   for(j=1;j<=m;j++)
    v1[a[i][j]]++;
   bad=0; badinit=0;

  for(i=0;i<=27;i++)
   if (v1[i]!=def[i]) badinit++;

  for(i=m;i<=n;i++)
   {
     if (i>m)
      for(c=1;c<=m;c++)
       { if (v1[a[i][c]]+1==def[a[i][c]]) badinit--;
         if (v1[a[i][c]]==def[a[i][c]]) badinit++;
        v1[a[i][c]]++;
         if (v1[a[i-m][c]]-1==def[a[i-m][c]]) badinit--;
         if (v1[a[i-m][c]]==def[a[i-m][c]]) badinit++;
        v1[a[i-m][c]]--;}

    if (!badinit) sol++;

      bad=badinit;

    for(j=0;j<=27;j++) v2[j]=v1[j];

      for(j=m+1;j<=n;j++)
      {
          for(l=i-m+1;l<=i;l++)
           {if (v2[a[l][j]]+1==def[a[l][j]]) bad--;
            if (v2[a[l][j]]==def[a[l][j]]) bad++;
            v2[a[l][j]]++;
            if (v2[a[l][j-m]]-1==def[a[l][j-m]]) bad--;
            if (v2[a[l][j-m]]==def[a[l][j-m]]) bad++;
            v2[a[l][j-m]]--;
           }

        if (!bad) sol++;
      }


   }

g<<sol;

}
int main()
{ Read();
  Solve();
   /*for(int i=1;i<=n;i++)
  {for(int j=1;j<=n;j++)
   cout<<a[i][j]<<" ";
   cout<<"\n";
  }*/

    return 0;
}