Cod sursa(job #4899)

Utilizator megabyteBarsan Paul megabyte Data 8 ianuarie 2007 19:25:37
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#define NMAX 1024
#define INF "matrix.in"
#define OUF "matrix.out"
#define SG 26
using namespace std;
char hum[NMAX][NMAX],c;
unsigned long i,j,n,m,k,val;
unsigned long v[SG]={0},lt[NMAX][NMAX]={0},bif[NMAX][NMAX]={0},nr=0;

main()
{
  fstream in(INF,ios::in);
  fstream out(OUF,ios::out);
  in>>m>>n;
  for(i=1;i<=m;i++)
   for(j=1;j<=m;j++)      in>>hum[i][j];
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)      {in>>c;v[(unsigned)c-97]++;} 
  for(k=0;k<SG;k++)
  {
     for(i=1;i<=m;i++)
      for(j=1;j<=m;j++){ 
                         lt[i][j]=lt[i][j-1]+lt[i-1][j]-lt[i-1][j-1];
                         if((unsigned)hum[i][j]-97==k) lt[i][j]+=1;
			}
     for(i=n;i<=m;i++)
      for(j=n;j<=m;j++)
       {
         val=lt[i][j]-lt[i][j-n]-lt[i-n][j]+lt[i-n][j-n];
	 if(val!=v[k]) bif[i][j]=1;
       } 
   }
  for(i=n;i<=m;i++)
   for(j=n;j<=m;j++) if(bif[i][j]) nr++;
  out<<(m-n+1)*(m-n+1)-nr;
  in.close();out.close();
  return 0;
}