Cod sursa(job #868309)

Utilizator dariusdariusMarian Darius dariusdarius Data 30 ianuarie 2013 21:42:57
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<string.h>
using namespace std;
int f[26];
char ch,a[1005][1005];
bool no[1005][1005];
int d[1005][1005];
int main()
{
    ifstream cin("matrix.in");
    ofstream cout("matrix.out");
    int nr=0,n,m,i,j,letter;
    cin>>n>>m;cin.ignore();
    for(i=1;i<=n;i++,cin.ignore())
        for(j=1;j<=n;j++)
            cin>>a[i][j];
    for(i=1;i<=m;i++,cin.ignore())
        for(j=1;j<=m;j++)
        {
            cin>>ch;
            f[ch-'a']++;
        }
    ///  no[i][j]= 1, daca in i,j nu se termina un virus
    ///            0, daca in i,j se termina un virus
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i<m || j<m)
                no[i][j]=true;
    for(letter=0;letter<26;letter++)
    {
        memset(d,0,sizeof(d));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(a[i][j]==letter+'a');
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i>=m && j>=n && d[i][j]-d[i-m][j]-d[i][j-m]+d[i-m][j-m]!=f[letter])
                    no[i][j]=true;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(!no[i][j])
                nr++;
    cout<<nr<<endl;
    return 0;
}