Cod sursa(job #492172)

Utilizator ChallengeMurtaza Alexandru Challenge Data 13 octombrie 2010 17:39:01
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="matrix.in";
const char OutFile[]="matrix.out";
const int MaxN=1005;

ifstream fin(InFile);
ofstream fout(OutFile);

char a[MaxN][MaxN],buffer[MaxN];
int psum[MaxN][MaxN],N,M,virus[26],sol,m[26];
char msol[MaxN][MaxN];

int main()
{
    fin>>N>>M;
    for(register int i=0;i<N;++i)
    {
        fin>>a[i];
    }
    for(register int i=0;i<M;++i)
    {
        fin>>buffer;
        for(register int j=0;j<=M;++j)
        {
            ++virus[buffer[j]-'a'];
        }
    }
    fin.close();

    for(register int k=0;k<26;++k)
    {
        for(register int i=1;i<=N;++i)
        {
            for(register int j=1;j<=N;++j)
            {
                psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1];
                if(a[i-1][j-1]-'a'==k)
                {
                    ++psum[i][j];
                }

                if(i>=M && j>=M)
                {
                    if(psum[i][j]-psum[i-M][j]-psum[i][j-M]+psum[i-M][j-M]!=virus[k])
                    {
                        msol[i][j]=1;
                    }
                }
            }
        }
    }

    for(register int i=M;i<=N;++i)
    {
        for(register int j=M;j<=N;++j)
        {
            if(msol[i][j]==0)
            {
                ++sol;
            }
        }
    }

    fout<<sol;
    fout.close();
    return 0;
}