Cod sursa(job #2681405)

Utilizator eugen5092eugen barbulescu eugen5092 Data 5 decembrie 2020 13:18:44
Problema Matrix Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>
using namespace std;

ifstream ci("matrix.in");
ofstream cou("matrix.out");
//m e matri umana n e matr virus
//tin pt fiec colt de matrice n*n frecv literelor

int n,m;
int a[1005][1005];

int fr[1005][1005][50];
int virus[50];

void citire(){
    ci>>m>>n;
    char c;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            ci>>c;
            a[i][j]=c-'a'+1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ci>>c;
            virus[c-'a'+1]++;
        }
    }
}

void afis(){
    for(int i=n;i<=m;i++){
        for(int j=n;j<=m;j++){
            cout<<i<<" "<<j<<" \n";
            for(int p=1;p<=10;p++){
                cout<<fr[i][j][p]<<" ";
            }
            cout<<"\n";
        }
    }
}

void fafr(){
    int p;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            p=a[i][j];
            fr[n][n][p]++;
        }
    }
    for(int i=n;i<=m;i++){
        for(int j=n;j<=m;j++){
            //scadem coloana j-n
            //adunam coloana j
            //fr[i][j][]'
            if(i==n&&j==n){
                j++;
            }
            if(j>n){
                //parc coloane punem f init
                for(int p=1;p<=40;p++){
                    fr[i][j][p]=fr[i][j-1][p];
                }
                //adaugam coloana j
                int x;
                for(int t=i;t>=i-n+1;t--){
                    x=a[t][j];
                    fr[i][j][x]++;
                }
                //scadem coloana j-n
                for(int t=i;t>=i-n+1;t--){
                    x=a[t][j-n];
                    fr[i][j][x]--;
                }
            }else{
                //daca j==n inseaman ca e linie noua deci :
                ///adunam linia i
                ///scadem linia i-n
                for(int p=1;p<=40;p++){
                    fr[i][j][p]=fr[i-1][j][p];
                }
                //adaugam linia i
                int x;
                for(int t=j;t>=j-n+1;t--){
                    x=a[i][t];
                    fr[i][j][x]++;
                }
                //scadem coloana i-n
                for(int t=j;t>=j-n+1;t--){
                    x=a[i-n][t];
                    fr[i][j][x]--;
                }
            }

        }
    }
}

void rez(){
    int s,sol=0;
    for(int i=n;i<=m;i++){
        for(int j=n;j<=m;j++){
            s=1;
            for(int p=1;p<=40;p++){
                if(fr[i][j][p]!=virus[p]){
                    s=0;
                }
            }
            sol+=s;
        }
    }
    cou<<sol;
}

int main()
{
    citire();
    fafr();
    //afis();
    rez();
    return 0;
}