Cod sursa(job #2358047)

Utilizator canmihaiCancescu Mihai canmihai Data 27 februarie 2019 21:07:21
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int n,m,f[1010],fm[1010][1010],d[1010][1010],sol;
char c[1010][1010],x;
int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>c[i][j];
    for(int i=1;i<=m*m;i++){
        fin>>x;
        f[x]++;
    }
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            fm[i][j]=1;
        for(char ch='a';ch<='z';ch++){
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++){//d[i][j]=de cate ori apare un caracter din virus in subm  m*m cu coltul de jos i j
                    d[i][j]=(c[i][j]==ch)+d[i][j-1]+d[i-1][j]-d[i-1][j-1];
                //    cout<<d[i][j]<<" ";
                }


    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++){
            int t=d[i][j]-d[i-m][j]-d[i][j-m]+d[i-m][j-m];
          //  cout<<t;
            if(t!=f[ch])
                fm[i][j]=0;
        }
    }
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            sol+=fm[i][j];
    fout<<sol;

}