Cod sursa(job #2357810)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 27 februarie 2019 19:02:20
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
using namespace std;
ifstream fin ("matrix.in");
ofstream fout("matrix.out");

int d[1010][1010],ok[1010][1010],f[60],sol,n,m;
char c,patrat[1010][1010];

int main (){

    fin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            fin>>patrat[i][j];
        }
    }


    for (int i=1;i<=m;i++){
        for (int j=1;j<=m;j++) {
            fin>>c;
            f[c]++;
        }
     }

    for(int i=m;i<=n;i++){
        for(int j=m;j<=n;j++){
            ok[i][j]=1;
         }
    }


    for(c = 'a'; c <= 'z'; c++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
                if(patrat[i][j]==c){
                    d[i][j]++;
                }
            }
        }


        for (int i=m;i<=n;i++){
           for (int j=m;j<=n;j++){
                if (d[i][j]-d[i-m][j]-d[i][j-m]+d[i-m][j-m]!=f[c]){
                    ok[i][j]=0;
                }
            }
        }

    }

    for (int i=m;i<=n;i++){
        for (int j=m;j<=n;j++){
             sol+=ok[i][j];
         }
    }


    fout<<sol;

    return 0;
}