Cod sursa(job #2354907)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 25 februarie 2019 17:51:25
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("matrix.in");
ofstream fout ("matrix.out");

int n, m, i, j, sol;
int f[30];
int d[1005][1005];

bool bul[1005][1005];

char c, t, a[1005][1005];

int main(){
    fin >> n >> m;
    for (i=1; i<=n; i++){
        for (j=1; j<=n; j++){
            fin >> a[i][j];
        }
    }
    for (i=1; i<=m; i++){
        for (j=1; j<=m; j++){
            fin >> c;
            f[c]++;
        }
    }
    for (i=m; i<=n; i++){
        for (j=m; j<=n; j++){
            bul[i][j] = 1;
        }
    }
    for (t='a'; t<='z'; t++){
        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];
                if (a[i][j] == t){
                    d[i][j]++;
                }
            }
        }
        for (i=m; i<=n; i++){
            for (j=m; j<=n; j++){
                if (d[i][j] - d[i][j-m] - d[i-m][j] + d[i-m][j-m] != f[t]){
                    bul[i][j] = 0;
                }
            }
        }
    }
    for (i=m; i<=n; i++){
        for (j=m; j<=n; j++){
            sol += bul[i][j];
        }
    }
    fout << sol;
    return 0;
}