Cod sursa(job #1236406)

Utilizator diana97Diana Ghinea diana97 Data 1 octombrie 2014 21:53:16
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("matrix.in");
ofstream g ("matrix.out");

const int NMAX = 1000 + 1;

int m, n, sol;
int ap[28];
char v[NMAX][NMAX];
int fr[NMAX][NMAX], apare[NMAX][NMAX];

void citeste() {
    f >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++) f >> v[i][j];
    char x;
    int l = n * n;
    for (int i = 1; i <= l; i++) {
        f >> x;
        ap[x - 'a' + 1]++;
    }
}

void rezolva() {
    for (int i = n; i <= m; i++)
        for (int j = n; j <= m; j++) apare[i][j] = 1;
    for (int c = 1; c <= 26; c++) {
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++) {
                if (v[i][j] - 'a' + 1 == c) fr[i][j] = 1;
                else fr[i][j] = 0;
                fr[i][j] += fr[i - 1][j] + fr[i][j - 1] - fr[i - 1][j - 1];
            }
        for (int i = n; i <= m; i++)
            for (int j = n; j <= m; j++)
                if (fr[i][j] - fr[i][j - n] - fr[i - n][j] + fr[i - n][j - n] != ap[c]) apare[i][j] = 0;
    }

    for (int i = n; i <= m; i++)
        for (int j = n; j <= m; j++)
            if (apare[i][j] == 1) sol++;
    g << sol << '\n';
}

int main() {
    citeste();
    rezolva();
    return 0;
}