Cod sursa(job #1261024)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 11 noiembrie 2014 21:11:53
Problema Matrix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#define MAXN 1000
#define NRCH 26
int m[MAXN+1][MAXN+1], ok[MAXN+1][MAXN+1], fr[NRCH], s[MAXN+1][MAXN+1];
int main(){
    int n, k, i, j, sum, c;
    FILE *fin, *fout;
    fin=fopen("matrix.in", "r");
    fout=fopen("matrix.out", "w");
    fscanf(fin, "%d%d", &k, &n);
    for(i=1; i<=k; i++){
        fgetc(fin);
        for(j=1; j<=k; j++){
            m[i][j]=fgetc(fin)-'a';
        }
    }
    for(i=0; i<n; i++){
        fgetc(fin);
        for(j=0; j<n; j++){
            fr[fgetc(fin)-'a']++;
        }
    }
    for(c=0; c<NRCH; c++){
        for(i=1; i<=k; i++){
            for(j=1; j<=k; j++){
                s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+(m[i][j]==c);
                if((ok[i][j]==c)&&(s[i][j]==fr[c])){
                    ok[i][j]=c+1;
                }
            }
        }
        for(i=n; i<=k; i++){
            for(j=n; j<=k; j++){
                if((ok[i][j]==c)&&(s[i][j]-s[i-n][j]-s[i][j-n]+s[i-n][j-n]==fr[c])){
                    ok[i][j]=c+1;
                }
            }
        }
    }
    sum=0;
    for(i=1; i<=k; i++){
        for(j=1; j<=k; j++){
            sum+=(ok[i][j]==NRCH);
        }
    }
    fprintf(fout, "%d\n", sum);
    fclose(fin);
    fclose(fout);
    return 0;
}