Cod sursa(job #3165909)

Utilizator radu._.21Radu Pelea radu._.21 Data 7 noiembrie 2023 09:53:55
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>


using namespace std;
int n,m,f[200],sp[1001][1001];
ifstream fin("matrix.in");
ofstream fout("matrix.out");
bool ok[1001][1001];
char a[1001][1001];
int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>a[i][j];
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++){
        char c; fin>>c;
        f[c]++;
    }
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            ok[i][j]=1;
    for(char c = 'a';c<='z';c++){

       /// fac sp pt c
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];
                if(a[i][j]==c)
                    sp[i][j]++;
            }
        for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++){
            int is=i-m+1 ,js=j-m+1 ,ij=i,jj=j;
            int s = sp[ij][jj] - sp[is-1][jj] - sp[ij][js-1] + sp[is-1][js-1];
            if(s!=f[c])
                ok[i][j]=0;
        }
    }
    int rez=0;
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            rez+=ok[i][j];
    fout<<rez;
    return 0;
}